The Experts below are selected from a list of 1470 Experts worldwide ranked by ideXlab platform
Michael A. Henning - One of the best experts on this subject based on the ideXlab platform.
-
maker breaker Total Domination game
Discrete Applied Mathematics, 2020Co-Authors: Valentin Gledel, Michael A. Henning, Sandi Klavžar, Vesna IršičAbstract:Abstract The Maker–Breaker Total Domination game in graphs is introduced as a natural counterpart to the Maker–Breaker Domination game recently studied by Duchene, Gledel, Parreau, and Renault. Both games are instances of the combinatorial Maker–Breaker games. The Maker–Breaker Total Domination game is played on a graph G by two players who alternately take turns choosing vertices of G . The first player, Dominator, selects a vertex in order to Totally dominate G while the other player, Staller, forbids a vertex to Dominator in order to prevent him from reaching his goal. It is shown that there are infinitely many connected cubic graphs in which Staller wins and that no minimum degree condition is sufficient to guarantee that Dominator wins when Staller starts the game. An amalgamation lemma is established and used to determine the outcome of the game played on grids. Cacti are also classified with respect to the outcome of the game. A connection between the game and hypergraphs is established. It is proved that the game is PSPACE-complete on split and bipartite graphs. Several problems and questions are also posed.
-
Maker-Breaker Total Domination game
2019Co-Authors: Valentin Gledel, Michael A. Henning, Vesna Iršič, Sandi KlavžarAbstract:Maker-Breaker Total Domination game in graphs is introduced as a natural counterpart to the Maker-Breaker Domination game recently studied by Duchêne, Gledel, Parreau, and Renault. Both games are instances of the com-binatorial Maker-Breaker games. The Maker-Breaker Total Domination game is played on a graph G by two players who alternately take turns choosing vertices of G. The first player, Dominator, selects a vertex in order to Totally dominate G while the other player, Staller, forbids a vertex to Dominator in order to prevent him to reach his goal. It is shown that there are infinitely many connected cubic graphs in which Staller wins and that no minimum degree condition is sufficient to guarantee that Dominator wins when Staller starts the game. An amalgamation lemma is established and used to determine the outcome of the game played on grids. Cacti are also classified with respect to the outcome of the game. A connection between the game and hypergraphs is established. It is proved that the game is PSPACE-complete on split and bipartite graphs. Several problems and questions are also posed.
-
maker breaker Total Domination game
arXiv: Combinatorics, 2019Co-Authors: Valentin Gledel, Michael A. Henning, Sandi Klavžar, Vesna IršičAbstract:Maker-Breaker Total Domination game in graphs is introduced as a natural counterpart to the Maker-Breaker Domination game recently studied by Duchene, Gledel, Parreau, and Renault. Both games are instances of the combinatorial Maker-Breaker games. The Maker-Breaker Total Domination game is played on a graph $G$ by two players who alternately take turns choosing vertices of $G$. The first player, Dominator, selects a vertex in order to Totally dominate $G$ while the other player, Staller, forbids a vertex to Dominator in order to prevent him to reach his goal. It is shown that there are infinitely many connected cubic graphs in which Staller wins and that no minimum degree condition is sufficient to guarantee that Dominator wins when Staller starts the game. An amalgamation lemma is established and used to determine the outcome of the game played on grids. Cacti are also classified with respect to the outcome of the game. A connection between the game and hypergraphs is established. It is proved that the game is PSPACE-complete on split and bipartite graphs. Several problems and questions are also posed.
-
game Total Domination critical graphs
Discrete Applied Mathematics, 2018Co-Authors: Michael A. Henning, Sandi Klavžar, Douglas F RallAbstract:Abstract In the Total Domination game played on a graph G , players Dominator and Staller alternately select vertices of G , as long as possible, such that each vertex chosen increases the number of vertices Totally dominated. Dominator (Staller) wishes to minimize (maximize) the number of vertices selected. The game Total Domination number, γ tg ( G ) , of G is the number of vertices chosen when Dominator starts the game and both players play optimally. If a vertex v of G is declared to be already Totally dominated, then we denote this graph by G | v . In this paper the Total Domination game critical graphs are introduced as the graphs G for which γ tg ( G | v ) γ tg ( G ) holds for every vertex v in G . If γ tg ( G ) = k , then G is called k - γ tg -critical. It is proved that the cycle C n is γ tg -critical if and only if n ( mod 6 ) ∈ { 0 , 1 , 3 } and that the path P n is γ tg -critical if and only if n ( mod 6 ) ∈ { 2 , 4 } . 2- γ tg -critical and 3- γ tg -critical graphs are also characterized as well as 3- γ tg -critical joins of graphs.
-
Total Domination stability in graphs
Discrete Applied Mathematics, 2018Co-Authors: Michael A. Henning, Marcin KrzywkowskiAbstract:Abstract A set D of vertices in an isolate-free graph G is a Total dominating set of G if every vertex is adjacent to a vertex in D . The Total Domination number, γ t ( G ) , of G is the minimum cardinality of a Total dominating set of G . We note that γ t ( G ) ≥ 2 for every isolate-free graph G . A non-isolating set of vertices in G is a set of vertices whose removal from G produces an isolate-free graph. The γ t − -stability, denoted st γ t − ( G ) , of G is the minimum size of a non-isolating set S of vertices in G whose removal decreases the Total Domination number. We show that if G is a connected graph with maximum degree Δ satisfying γ t ( G ) ≥ 3 , then st γ t − ( G ) ≤ 2 Δ − 1 , and we characterize the infinite family of trees that achieve equality in this upper bound. The Total Domination stability, st γ t ( G ) , of G is the minimum size of a non-isolating set of vertices in G whose removal changes the Total Domination number. We prove that if G is a connected graph with maximum degree Δ satisfying γ t ( G ) ≥ 3 , then st γ t ( G ) ≤ 2 Δ − 1 .
Nader Jafari Rad - One of the best experts on this subject based on the ideXlab platform.
-
A note on neighborhood Total Domination in graphs
Proceedings - Mathematical Sciences, 2015Co-Authors: Nader Jafari RadAbstract:Let G =( V , E ) be a graph without isolated vertices. A dominating set S of G is called a neighborhood Total dominating set (or just NTDS) if the induced subgraph G [ N ( S )] has no isolated vertex. The minimum cardinality of a NTDS of G is called the neighborhood Total Domination number of G and is denoted by γ _nt( G ). In this paper, we obtain sharp bounds for the neighborhood Total Domination number of a tree. We also prove that the neighborhood Total Domination number is equal to the Domination number in several classes of graphs including grid graphs.
-
bounds on neighborhood Total Domination in graphs
Discrete Applied Mathematics, 2013Co-Authors: Michael A. Henning, Nader Jafari RadAbstract:In this paper, we continue the study of neighborhood Total Domination in graphs first studied by Arumugam and Sivagnanam [S. Arumugam, C. Sivagnanam, Neighborhood Total Domination in graphs, Opuscula Math. 31 (2011) 519-531]. A neighborhood Total dominating set, abbreviated NTD-set, in a graph G is a dominating set S in G with the property that the subgraph induced by the open neighborhood of the set S has no isolated vertex. The neighborhood Total Domination number, denoted by @c"n"t(G), is the minimum cardinality of a NTD-set of G. Every Total dominating set is a NTD-set, implying that @c(G)@?@c"n"t(G)@?@c"t(G), where @c(G) and @c"t(G) denote the Domination and Total Domination numbers of G, respectively. We show that if G is a connected graph on n>=3 vertices, then @c"n"t(G)@?(n+1)/2 and we characterize the graphs achieving equality in this bound.
-
On α-Total Domination in graphs
Discrete Applied Mathematics, 2011Co-Authors: Michael A. Henning, Nader Jafari RadAbstract:Let G=(V,E) be a graph with no isolated vertex. A subset of vertices S is a Total dominating set if every vertex of G is adjacent to some vertex of S. For some @a with 0 [email protected]|N(v)|. The minimum cardinality of an @a-Total dominating set of G is called the @a-Total Domination number of G. In this paper, we study @a-Total Domination in graphs. We obtain several results and bounds for the @a-Total Domination number of a graph G.
-
Total Domination dot-critical graphs
Discrete Applied Mathematics, 2010Co-Authors: Michael A. Henning, Nader Jafari RadAbstract:A graph G with no isolated vertex is Total Domination vertex-critical if for any vertex v of G that is not adjacent to a vertex of degree one, the Total Domination number of G-v is less than the Total Domination number of G. A graph is Total Domination dot-critical if contracting any edge decreases the Total Domination number. In this paper, we study Total Domination dot-critical graphs. We present several properties of these graphs. We show that the Total Domination dot-critical graphs include the Total Domination vertex-critical graphs.
-
Locating-Total Domination critical graphs.
2009Co-Authors: Mustapha Chellali, Nader Jafari RadAbstract:A locating-Total dominating set of a graph G = (V (G), E(G)) with no isolated vertex is a set S ⊆ V (G) such that every vertex of V (G) is adjacent to a vertex of S and for every pair of distinct vertices u and v in V (G) − S, N(u) ∩ S = N(v) ∩ S. Let γ t (G) be the minimum cardinality of a locating-Total dominating set of G. A graph G is said to be locating-Total Domination vertex critical if for every vertex w that is not a support vertex, γ t (G−w) < γ t (G). Locating-Total Domination edge critical graphs are defined similarly. In this paper, we study locating-Total Domination critical graphs.
Teresa W. Haynes - One of the best experts on this subject based on the ideXlab platform.
-
Edge lifting and Total Domination in graphs
Journal of Combinatorial Optimization, 2013Co-Authors: Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. HenningAbstract:Let u and v be vertices of a graph G , such that the distance between u and v is two and x is a common neighbor of u and v . We define the edge lift of uv off x as the process of removing edges ux and vx while adding the edge uv to G . In this paper, we investigate the effect that edge lifting has on the Total Domination number of a graph. Among other results, we show that there are no trees for which every possible edge lift decreases the Total Domination number and that there are no trees for which every possible edge lift leaves the Total Domination number unchanged. Trees for which every possible edge lift increases the Total Domination number are characterized.
-
Total Domination changing and stable graphs upon vertex removal
Discrete Applied Mathematics, 2011Co-Authors: Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. HenningAbstract:A set S of vertices in a graph G is a Total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a Total dominating set of G is the Total Domination number of G. A graph is Total Domination vertex removal stable if the removal of an arbitrary vertex leaves the Total Domination number unchanged. On the other hand, a graph is Total Domination vertex removal changing if the removal of an arbitrary vertex changes the Total Domination number. In this paper, we study Total Domination vertex removal changing and stable graphs.
-
Total Domination dot-stable graphs
Discrete Applied Mathematics, 2011Co-Authors: Stephanie A. Rickett, Teresa W. HaynesAbstract:A set S of vertices in a graph G is a Total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a Total dominating set of G is the Total Domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the Total Domination number. Further we show it can decrease the Total Domination number by at most 2. A graph is Total Domination dot-stable if dotting any pair of adjacent vertices leaves the Total Domination number unchanged. We characterize the Total Domination dot-stable graphs and give a sharp upper bound on their Total Domination number. We also characterize the graphs attaining this bound.
-
An extremal problem for Total Domination stable graphs upon edge removal
Discrete Applied Mathematics, 2011Co-Authors: Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. HenningAbstract:A connected graph is Total Domination stable upon edge removal, if the removal of an arbitrary edge does not change the Total Domination number. We determine the minimum number of edges required for a Total Domination stable graph in terms of its order and Total Domination number.
-
Total Domination stable graphs upon edge addition
Discrete Mathematics, 2010Co-Authors: Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. HenningAbstract:AbstractA set S of vertices in a graph G is a Total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a Total dominating set of G is the Total Domination number of G. A graph is Total Domination edge addition stable if the addition of an arbitrary edge has no effect on the Total Domination number. In this paper, we characterize Total Domination edge addition stable graphs. We determine a sharp upper bound on the Total Domination number of Total Domination edge addition stable graphs, and we determine which combinations of order and Total Domination number are attainable. We finish this work with an investigation of claw-free Total Domination edge addition stable graphs
Anders Yeo - One of the best experts on this subject based on the ideXlab platform.
-
Total Domination in graphs
2013Co-Authors: Michael A. Henning, Anders YeoAbstract:1. Introduction.- 2. Properties of Total Dominating Sets and General Bounds.- 3. Complexity and Algorithmic Results.- 4.Total Domination in Trees.- 5.Total Domination and Minimum Degree.- 6. Total Domination in Planar Graphs.- 7. Total Domination and Forbidden Cycles.- 8. Relating the Size and Total Domination Number.- 9. Total Domination in Claw-Free Graphs.- 10. Total Domination Number versus Matching Number.- 11. Total Domination Critical Graphs.- 12. Total Domination and Graph Products.- 13. Graphs with Disjoint Total Dominating Sets.- 14. Total Domination in Graphs with Diameter Two.- 15. Nordhaus-Gaddum Bounds for Total Domination.- 16. Upper Total Domination.- 17.Variations of Total Domination.- 18. Conjectures and Open Problems.- Index.
-
Total Domination in Trees
Springer Monographs in Mathematics, 2013Co-Authors: Michael A. Henning, Anders YeoAbstract:In this chapter, we present results on Total Domination in trees. For a linear algorithm to compute the Total Domination of a tree, see Sect. 3.5.
-
Total Domination in Planar Graphs
Springer Monographs in Mathematics, 2013Co-Authors: Michael A. Henning, Anders YeoAbstract:In the metadata of the chapter that will be visualized online, please change the abstract to read as follows: “In this chapter, we look at Total Domination in planar graphs.”
-
Total Domination Critical Graphs
Springer Monographs in Mathematics, 2013Co-Authors: Michael A. Henning, Anders YeoAbstract:For many graph parameters, criticality is a fundamental question. Much has been written about those graphs where a parameter (such as connectedness or chromatic number) goes up or down whenever an edge or vertex is removed or added. In this chapter, we consider the same concept for Total Domination.
-
Total Domination and Forbidden Cycles
Springer Monographs in Mathematics, 2013Co-Authors: Michael A. Henning, Anders YeoAbstract:In the metadata of the chapter that will be visualized online, please make the following change:“In this chapter, we investigate upper bounds on the Total Domination number of a graph given certain forbidden cycles”
Adel P. Kazemi - One of the best experts on this subject based on the ideXlab platform.
-
Double Total Domination in Harary Graphs
arXiv: Combinatorics, 2016Co-Authors: Adel P. Kazemi, Behnaz PahlavsayAbstract:Let $G$ be a graph with minimum degree at least 2. A set $D\subseteq V$ is a double Total dominating set of $G$ if each vertex is adjacent to at least two vertices in $D$. The double Total Domination number $\gamma _{\times 2,t}(G)$ of $G$ is the minimum cardinality of a double Total dominating set of $G$. In this paper, we will find double Total Domination number of Harary graphs.
-
Upper k-tuple Total Domination in graphs
arXiv: Combinatorics, 2016Co-Authors: Adel P. KazemiAbstract:Let $G=(V,E)$ be a simple graph. For any integer $k\geq 1$, a subset of $V$ is called a $k$-tuple Total dominating set of $G$ if every vertex in $V$ has at least $k$ neighbors in the set. The minimum cardinality of a minimal $k$-tuple Total dominating set of $G$ is called the $k$-tuple Total Domination number of $G$. In this paper, we introduce the concept of upper $k$-tuple Total Domination number of $G$ as the maximum cardinality of a minimal $k$-tuple Total dominating set of $G$, and study the problem of finding a minimal $k$-tuple Total dominating set of maximum cardinality on several classes of graphs, as well as finding general bounds and characterizations. Also, we find some results on the upper $k$-tuple Total Domination number of the Cartesian and cross product graphs.
-
$k$-Tuple Total Domination Number of Cartesian Product Graphs
arXiv: Combinatorics, 2015Co-Authors: Adel P. Kazemi, Behnaz PahlavsayAbstract:The most famous open problem involving Domination in graphs is Vizing's conjecture which states the Domination number of the Cartesian product of any two graphs is at least as large as the product of their Domination numbers. In this paper, we investigate a similar problem for the k-tuple Total Domination number. Then we calculate the k-tuple Total Domination number of the Cartesian product of two complete graphs.
-
Total Domination in inflated graphs
Discrete Applied Mathematics, 2012Co-Authors: Michael A. Henning, Adel P. KazemiAbstract:AbstractThe inflation GI of a graph G is obtained from G by replacing every vertex x of degree d(x) by a clique X=Kd(x) and each edge xy by an edge between two vertices of the corresponding cliques X and Y of GI in such a way that the edges of GI which come from the edges of G form a matching of GI. A set S of vertices in a graph G is a Total dominating set, abbreviated TDS, of G if every vertex of G is adjacent to a vertex in S. The minimum cardinality of a TDS of G is the Total Domination number γt(G) of G. In this paper, we investigate Total Domination in inflated graphs. We provide an upper bound on the Total Domination number of an inflated graph in terms of its order and matching number. We show that if G is a connected graph of order n≥2, then γt(GI)≥2n/3, and we characterize the graphs achieving equality in this bound. Further, if we restrict the minimum degree of G to be at least 2, then we show that γt(GI)≥n, with equality if and only if G has a perfect matching. If we increase the minimum degree requirement of G to be at least 3, then we show γt(GI)≥n, with equality if and only if every minimum TDS of GI is a perfect Total dominating set of GI, where a perfect Total dominating set is a TDS with the property that every vertex is adjacent to precisely one vertex of the set
-
k-tuple Total Domination in cross products of graphs
Journal of Combinatorial Optimization, 2011Co-Authors: Michael A. Henning, Adel P. KazemiAbstract:For k?1 an integer, a set S of vertices in a graph G with minimum degree at least k is a k-tuple Total dominating set of G if every vertex of G is adjacent to at least k vertices in S. The minimum cardinality of a k-tuple Total dominating set of G is the k-tuple Total Domination number of G. When k=1, the k-tuple Total Domination number is the well-studied Total Domination number. In this paper, we establish upper and lower bounds on the k-tuple Total Domination number of the cross product graph G×H for any two graphs G and H with minimum degree at least k. In particular, we determine the exact value of the k-tuple Total Domination number of the cross product of two complete graphs.
