On 2-Movable Total Domination in the Join and Corona of Graphs

2025

Read On 2-Movable Total Domination in the Join and Corona of Graphs (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-10952.txt.

Introduction

Ariel Pedrano and Rolando Paluga study a strong form of domination in graphs, where a set of points must cover the whole graph even after moves. A total dominating set reaches every point through a neighbor. Their version must still work after any two members are removed or swapped for suitable points outside the set.

The paper works out this number for two ways of combining graphs: the join, which links two graphs fully, and the corona, which attaches copies of one graph to points of another. Results like these extend graph theory tools used to place guards, sensors, or shared resources so a network stays covered under change.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-10952

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On 2-Movable Total Domination in the Join and Corona of Graphs Abstract Let G G be a connected graph. A non-empty T ⊆ V ⁡ ( G ) T\subseteq V(G) is a 2 2 - movable total dominating set of G G if T T is a total dominating set and for every pair x , y ∈ T x,y\in T , T \ { x , y } T\backslash\{x,y\} is a total dominating set in G G , or there exist u , v ∈ V ⁡ ( G ) \ T u,v\in V(G)\backslash T such that u u and v v are adjacent to x x and y y , respectively, and ( T \ { x , y } ) ∪ { u , v } (T\backslash\{x,y\})\cup\{u,v\} is a total dominating set in G G . The 2 2 - movable total domination number of G G , denoted by γ m ​ t 2 ​ ( G ) \gamma_{mt}^{2}(G) , is the minimum cardinality of a 2-movable total dominating set of G G . A 2-movable total dominating set with cardinality equal to γ m ​ t 2 ​ ( G ) \gamma_{mt}^{2}(G) is called γ m ​ t 2 \gamma_{mt}^{2} -set of G G . This paper present the 2-movable total domination in the join and corona of graphs. Ariel C. Pedrano Mathematics and Statistics Department College of Arts and Sciences University of Southeastern Philippines Davao City, Philippines Rolando N. Paluga Mathematics Department College of Mathematics and Natural Sciences Caraga State University Butuan City, Philippines email: [email protected], [email protected] 1 Introduction All graphs considered in this paper are all connected, finite, simple and undirected. Let G=(V,E) be a connected, finite, simple and undirected graph. The graph G has a vertex set V=V(G) and an edge set E=E(G) . Further, let the order of the graph G be p , that is, |V|=|V(G)|=p and the size of the graph G be q , that is, |E|=|E(G)|=q . One of the interesting fields of Graph Theory is graph domination. Several variants of domination has been introduced and explored such as total domination [ 2 ] , 1-movable domination in graphs [ 4 ] , neighborhoud transversal domination of some graphs [ 3 ] and others. Inspired by the study of Blair et. al [ 1 ] about 1-movable domination, Pedrano and Paluga [ 7 ] defined a new variant of domination and called it 2-movable domination. A non-empty S\subseteq V(G) is a 2 - movable dominating set of G if S is a dominating set and for every pair x,y\in S , S\backslash\{x,y\} is a dominating set in G , or there exist u,v\in V(G)\backslash S such that u and v are adjacent to x and y , respectively, and (S\backslash\{x,y\})\cup\{u,v\} is a dominating set in G . The 2 - movable domination number of G , denoted by \gamma_{m}^{2}(G) , is the minimum cardinality of a 2-movable dominating set of G . A 2-movable dominating set with cardinality equal to \gamma_{m}^{2}(G) is called \gamma_{m}^{2} -set of G . In this study, the concept of 2-movable total domination in a graph will be introduced and initially investigated. In particular, the 2-movable total domination number will be given for the join and corona of graphs. 2 Basic Concepts Definition 2.1 . [ 4 ] A subset S of V(G) is a dominating set of G if for every v\in V(G)\backslash S , there exists u\in S such that uv\in E(G) , that is, N_{G}[S]=V(G) . The domination number of G is denoted by \gamma(G) which refers to the smallest cardinality of a dominating set of G . A dominating set of G with cardinality equal to \gamma(G) is called a \gamma- set of G . Definition 2.2 . [ 2 ] Let G be a graph without isolated vertices. A subset S of V(G) is a total dominating set of G if N_{G}(S)=V(G) . That is, every vertex in V(G) is adjacent to some vertex in S . Definition 2.3 . [ 7 ] Let G be a connected graph. A non-empty T\subseteq V(G) is a 2 -movable total dominating set of G if T is a total dominating set and for every pair x,y\in T , T\backslash\{x,y\} is a total dominating set in G , or there exist u,v\in V(G)\backslash T such that u and v are adjacent to x and y , respectively, and (T\backslash\{x,y\})\cup\{u,v\} is a total dominating set in G . The 2 -movable total domination number of G , denoted by \gamma_{mt}^{2}(G) , is the minimum cardinality of a 2-movable total dominating set of G . A 2-movable total dominating set with cardinality equal to \gamma_{mt}^{2}(G) is called \gamma_{mt}^{2} -set of G . 3 Main Results Theorem 3.1 . If S is a 2-movable total dominating set of G , then S is a 2-movable dominating set of G . Furthermore, \gamma_{m}^{2}(G)\leq\gamma_{mt}^{2}(G) . Proof. Suppose S is a 2-movable total dominating set of G . It follows that S is a total dominating set of G by Definition 2.3 . Thus, S is a dominating set of G . Since S is a 2-movable total dominating set of G , then for every a_{1},a_{2}\in S , there exists b_{1},b_{2}\in V(G)\backslash S such that a_{1}b_{1},a_{2}b_{2}\in E(G) and (S\backslash\{a_{1},a_{2}\})\cup\{b_{1},b_{2}\} is a total dominating set of G . It follows that (S\backslash\{a_{1},a_{2}\})\cup\{b_{1},b_{2}\} is a dominating set of G . Hence, S is 2-movable dominating set of G . Therefore, \gamma_{m}^{2}(G)\leq\gamma_{mt}^{2}(G). ∎ The next remark follows directly from Definition 2.3 : Remark 3.2 . For any connected graph G of order n\geq 4 , \gamma_{mt}^{2}(G)\geq 2 . Theorem 3.3 . Let G and H be graphs of order at least 2. Then \gamma_{mt}^{2}(G+H)=2 . Proof. Let G and H be graphs of order at least 2, where V(G+H)=V(G)\cup V(H) and |V(G+H)|\geq 4 . Let S=\{u,v\} where u\in V(G) and v\in V(H) . We want to show that S is a total dominating set of G+H . Let x\in V(G+H) . If x\in V(G) , then xv\in E(G+H) . If x\in V(H) , then xu\in E(G+H) . Therefore, S is a total dominating set of G+H . Now, since |V(G)|\geq 2 and |V(H)|\geq 2 , there exists u^{\prime}\in V(G) and v^{\prime}\in V(H) such that u\not=u^{\prime} and v\not=v^{\prime} . Thus, S^{\prime}=(S\backslash\{u,v\})\cup\{u^{\prime},v^{\prime}\}=\{u^{\prime},v^{\prime}\} . By following the same arguments above, S^{\prime} is a total dominating set of G+H . Hence, S is a 2-movable total dominating set of G+H . Therefore, \gamma_{mt}^{2}(G+H)\leq 2 . By Remark 3.2 , \gamma_{mt}^{2}(G+H)=2 . ∎ Theorem 3.4 . Let G be a graph of order at least 3. Then \gamma_{mt}^{2}(G+K_{1})=\gamma_{t}(G) . Proof. Let S be a \gamma_{t} -set of G . Let x\in V(G+K_{1}) . Suppose x\in V(G) . Since S is a total dominating set of G , there exists y\in S such that xy\in E(G) . Note that E(G)\subseteq E(G+K_{1}) . Thus, xy\in E(G+K_{1}) . Therefore, S is a total dominating set of G+K_{1} . Now, let x_{1},x_{2}\in S . We want to show that S is a 2-movable total dominating set of G+K_{1} . Since S is a \gamma_{t} -set of G , at least one of the following conditions hold: (i) S\backslash\{x_{1},x_{2}\}

Read the complete text