Search

In [16] Nowakowski and Rall listed a series of conjectures involving several different graph products. In particular, they conjectured that i (G × H) ≥ i (G) i (H) where i(G) is the independent domination number of G and G × H is the direct product of graphs G and H. We show this conjecture is false, and, in fact, construct pairs of graphs for which min { i (G) , i (H) } - i (G × H) is arbitrarily large. We also give the exact value of i (G × K n) when G is either a path or a cycle. [ABSTRACT FROM AUTHOR]

A graph G is well-covered if all maximal independent sets of G have the same cardinality. In 1992 Topp and Volkmann investigated the structure of well-covered graphs that have nontrivial factorizations with respect to some of the standard graph products. In particular, they showed that both factors of a well-covered direct product are also well-covered and proved that the direct product of two complete graphs (respectively, two cycles) is well-covered precisely when they have the same order (respectively, both have order 3 or 4). Furthermore, they proved that the direct product of two well-covered graphs with independence number one-half their order is well-covered. We initiate a characterization of nontrivial connected well-covered graphs G and H, whose independence numbers are strictly less than one-half their orders, such that their direct product G-H is well-covered. In particular, we show that in this case both G and H have girth 3 and we present several infinite families of such well-covered direct products. Moreover, we show that if G is a factor of any well-covered direct product, then G is a complete graph unless it is possible to create an isolated vertex by removing the closed neighborhood of some independent set of vertices in G. [ABSTRACT FROM AUTHOR]

A graph is well-dominated if all its minimal dominating sets have the same cardinality. In this paper we prove that at least one factor of every connected, well-dominated Cartesian product is a complete graph, which then allows us to give a complete characterization of the connected, well-dominated Cartesian products if both factors have order at least 2. In particular, we show that G □ H is well-dominated if and only if G □ H = P 3 □ K 3 or G □ H = K n □ K n for some n ≥ 2. [ABSTRACT FROM AUTHOR]

Abstract In this paper a relationship is established between the domination game and minimal edge cuts. It is proved that the game domination number of a connected graph can be bounded above in terms of the size of minimal edge cuts. In particular, if C a minimum edge cut of a connected graph G , then γ g (G) ≤ γ g (G ∖ C) + 2 κ ′ (G). Double-Staller graphs are introduced in order to show that this upper bound can be attained for graphs with a bridge. The obtained results are used to extend the family of known traceable graphs whose game domination numbers are at most one-half their order. Along the way two technical lemmas, which seem to be generally applicable for the study of the domination game, are proved. [ABSTRACT FROM AUTHOR]

In 1970, Plummer defined a well-covered graph to be a graph G in which all maximal independent sets are in fact maximum. Later Hartnell and Rall showed that if the Cartesian product G□H is well-covered, then at least one of G or H is well-covered. In this paper, we consider the problem of classifying all well-covered Cartesian products. In particular, we show that if the Cartesian product of two nontrivial, connected graphs of girth at least 4 is well-covered, then at least one of the graphs is K2. Moreover, we show that K2□K2 and C5□K2 are the only well-covered Cartesian products of nontrivial, connected graphs of girth at least 5. [ABSTRACT FROM AUTHOR]

In this paper, we define a new domination invariant on a graph G , which coincides with the ordinary independent domination number of the generalized prism G □ K k , called the k-rainbow independent domination number and denoted by γ ri k ( G ). Some bounds and exact values concerning this domination concept are determined. As a main result, we prove a Nordhaus–Gaddum-type theorem on the sum for 2-rainbow independent domination number, and show if G is a graph of order n  ≥ 3, then 5 ≤ γ ri 2 ( G ) + γ ri 2 ( G ¯ ) ≤ n + 3 , with both bounds being sharp. [ABSTRACT FROM AUTHOR]

In this paper, we continue the study of the total domination game in graphs introduced in Henning et al. (2015), where the players Dominator and Staller alternately select vertices of G . Each vertex chosen must strictly increase the number of vertices totally dominated, where a vertex totally dominates another vertex if they are neighbors. This process eventually produces a total dominating set S of G in which every vertex is totally dominated by a vertex in S . Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number, γ tg ( G ) , (respectively, Staller-start game total domination number, γ tg ′ ( G ) ) of G is the number of vertices chosen when Dominator (respectively, Staller) starts the game and both players play optimally. For general graphs G , sometimes γ tg ( G ) > γ tg ′ ( G ) . We show that if G is a forest with no isolated vertex, then γ tg ( G ) ≤ γ tg ′ ( G ) . Using this result, we characterize the trees with equal total domination and game total domination number. [ABSTRACT FROM AUTHOR]

If each minimal dominating set in a graph is a minimum dominating set, then the graph is called well-dominated. Since the seminal paper on well-dominated graphs appeared in 1988, the structure of well-dominated graphs from several restricted classes has been studied. In this paper we give a complete characterization of nontrivial direct products that are well-dominated. We prove that if a strong product is well-dominated, then both of its factors are well-dominated. When one of the factors of a strong product is a complete graph, the other factor being well-dominated is also a sufficient condition for the product to be well-dominated. Our main result gives a complete characterization of well-dominated Cartesian products in which at least one of the factors is a complete graph. In addition, we conjecture that this result is actually a complete characterization of the class of nontrivial, well-dominated Cartesian products. [ABSTRACT FROM AUTHOR]

In this paper, we continue the study of the total domination game in graphs introduced in Henning et al. (2015), where the players Dominator and Staller alternately select vertices of G . Each vertex chosen must strictly increase the number of vertices totally dominated, where a vertex totally dominates another vertex if they are neighbors. This process eventually produces a total dominating set S of G in which every vertex is totally dominated by a vertex in S . Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. 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. Henning et al. (in press) posted the 3 4 -Game Total Domination Conjecture that states that if G is a graph on n vertices in which every component contains at least three vertices, then γ tg ( G ) ≤ 3 4 n . In this paper, we prove this conjecture over the class of graphs G that satisfy both the condition that the degree sum of adjacent vertices in G is at least 4 and the condition that no two vertices of degree 1 are at distance 4 apart in G . In particular, we prove that by adopting a greedy strategy, Dominator can complete the total domination game played in a graph with minimum degree at least 2 in at most 3 n / 4 moves. [ABSTRACT FROM AUTHOR]

Abstract: An identifying code in a graph is a dominating set that also has the property that the closed neighborhood of each vertex in the graph has a distinct intersection with the set. The minimum cardinality of an identifying code in a graph is denoted . It was recently shown by Gravier, Moncel and Semri that . Letting be any integers, we consider identifying codes of the direct product . In particular, we answer a question of Klavžar and show the exact value of . [Copyright &y& Elsevier]

Abstract: A -rainbow dominating function of a graph is a map from to the set of all subsets of such that whenever is a vertex with . The -rainbow domination number of is the invariant , which is the minimum sum (over all the vertices of ) of the cardinalities of the subsets assigned by a -rainbow dominating function. We focus on the -rainbow domination number of the lexicographic product of graphs and prove sharp lower and upper bounds for this number. In fact, we prove the exact value of in terms of domination invariants of except for the case when and there exists a minimum -rainbow dominating function of such that there is a vertex in with the label . [Copyright &y& Elsevier]

A DD2-pair of a graph G is a pair (D, D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ⋃ D2 necessarily contains all vertices of the graph. [ABSTRACT FROM AUTHOR]

The domination game played on a graph G consists of two players, Dominator and Staller, who alternate taking turns choosing a vertex from G such that whenever a vertex is chosen by either player, at least one additional vertex is dominated. Dominator wishes to dominate the graph in as few steps as possible, and Staller wishes to delay the process as much as possible. The game domination number γg (G) (resp., γ'g(G)) is the number of vertices chosen when Dominator (resp., Staller) starts the game. An imagination strategy is developed as a general tool for proving results Oil the domination game. We show that for any graph G, γ(G) ≤ γg(G)≤ 2γ(G) - 1, and that all possible values can be realized. It is proved that for any graph G, γg(G) - 1 ≤γ'g(G) ≤ γg (G) + 2, and that most of the possibilities for mutual values of γg(G) and γ'g(G) can be realized. A connection with Vizing's conjecture is established, and a lower bound on the game domination number of an arbitrary Cartesian product is proved. Several problems and conjectures are also stated. [ABSTRACT FROM AUTHOR]

Abstract: For a positive integer , a -packing in a graph is a subset of vertices such that the distance between any two distinct vertices from is more than . The packing chromatic number of is the smallest integer such that the vertex set of can be partitioned as where is an -packing for each . It is proved that the planar triangular lattice and the three-dimensional integer lattice do not have finite packing chromatic numbers. [Copyright &y& Elsevier]

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 total domination. In particular, we prove that the product of the total domination numbers of any nontrivial tree and any graph without isolated vertices is at most twice the total domination number of their Cartesian product, and we characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

A graph is said to be well-edge-dominated if all its minimal edge dominating sets are minimum. It is known that every well-edge-dominated graph G is also equimatchable, meaning that every maximal matching in G is maximum. In this paper, we show that if G is a connected, triangle-free, nonbipartite, well-edge-dominated graph, then G is one of three graphs. We also characterize the well-edge-dominated split graphs and Cartesian products. In particular, we show that a connected Cartesian product G □ H is well-edge-dominated, where G and H have order at least 2, if and only if G □ H = K 2 □ K 2 . We also prove that the Cartesian product of two connected, nontrivial graphs is well-edge-dominated if and only if it is equimatchable. [ABSTRACT FROM AUTHOR]

A dominating (respectively, total dominating) set S of a digraph D is a set of vertices in D such that the union of the closed (respectively, open) out‐neighborhoods of vertices in S equals the vertex set of D. The minimum size of a dominating (respectively, total dominating) set of D is the domination (respectively, total domination) number of D, denoted γ(D) (respectively, γt(D)). The maximum number of pairwise disjoint closed (respectively, open) in‐neighborhoods of D is denoted by ρ(D) (respectively, ρo(D)). We prove that in digraphs whose underlying graphs have girth at least 7, the closed (respectively, open) in‐neighborhoods enjoy the Helly property, and use these two results to prove that in any ditree T (i.e., a digraph whose underlying graph is a tree), γt(T)=ρo(T) and γ(T)=ρ(T). By using the former equality we then prove that γt(G×T)=γt(G)γt(T), where G is any digraph and T is any ditree, each without a source vertex, and G×T is their direct product. From the equality γ(T)=ρ(T) we derive the bound γ(G□T)≥γ(G)γ(T), where G is an arbitrary digraph, T an arbitrary ditree and G□T is their Cartesian product. In general digraphs this Vizing‐type bound fails, yet we prove that for any digraphs G and H, where γ(G)≥γ(H), we have γ(G□H)≥12γ(G)(γ(H)+1). This inequality is sharp as demonstrated by an infinite family of examples. Ditrees T and digraphs H enjoying γ(T□H)=γ(T)γ(H) are also investigated. [ABSTRACT FROM AUTHOR]

The 2-packing number ρ 2 (G) of a graph G is the cardinality of a largest 2-packing of G and the open packing number ρ o (G) is the cardinality of a largest open packing of G , where an open packing (resp. 2-packing) is a set of vertices in G no two (closed) neighborhoods of which intersect. It is proved that if G is bipartite, then ρ o (G □ K 2) = 2 ρ 2 (G). For hypercubes, the lower bounds ρ 2 (Q n) ≥ 2 n − ⌊ log ⁡ n ⌋ − 1 and ρ o (Q n) ≥ 2 n − ⌊ log ⁡ (n − 1) ⌋ − 1 are established. These findings are applied to injective colorings of hypercubes. In particular, it is demonstrated that Q 9 is the smallest hypercube which is not perfect injectively colorable. It is also proved that γ t (Q 2 k × H) = 2 2 k − k γ t (H) , where H is an arbitrary graph with no isolated vertices. [ABSTRACT FROM AUTHOR]

A graph is well-dominated if all of its minimal dominating sets have the same cardinality. It is proved that there are exactly eleven connected, well-dominated, triangle-free graphs whose domination number is at most 3. We prove that at least one of the factors is well-dominated if the Cartesian product of two graphs is well-dominated. In addition, we show that the Cartesian product of two connected, triangle-free graphs is well-dominated if and only if both graphs are complete graphs of order 2. Under the assumption that at least one of the connected graphs G or H has no isolatable vertices, we prove that the direct product of G and H is well-dominated if and only if either G = H = K 3 or G = K 2 and H is either the 4-cycle or the corona of a connected graph. Furthermore, we show that the disjunctive product of two connected graphs is well-dominated if and only if one of the factors is a complete graph and the other factor has domination number at most 2. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The packing chromatic number χρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets Vi, i∈[k], where each Vi is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that ω(G)=a, χ(G)=b, and χρ(G)=c. If so, we say that (a, b, c) is realizable. It is proved that b=c≥3 implies a=b, and that triples (2,k,k+1) and (2,k,k+2) are not realizable as soon as k≥4. Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on χρ(G) in terms of Δ(G) and α(G) is also proved. [ABSTRACT FROM AUTHOR]

The packing chromatic number χ ρ ( G ) of a graph G is the smallest integer k such that there exists a k -vertex coloring of G in which any two vertices receiving color i are at distance at least i + 1 . It is proved that in the class of subcubic graphs the packing chromatic number is bigger than 13 , thus answering an open problem from Gastineau and Togni (2016). In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if S e ( G ) is the graph obtained from a graph G by subdividing its edge e , then χ ρ ( G ) ∕ 2 + 1 ≤ χ ρ ( S e ( G ) ) ≤ χ ρ ( G ) + 1 . [ABSTRACT FROM AUTHOR]

The orientable domination number, DOM (G) , of a graph G is the largest domination number over all orientations of G. In this paper, DOM is studied on different product graphs and related graph operations. The orientable domination number of arbitrary corona products is determined, while sharp lower and upper bounds are proved for Cartesian and lexicographic products. A result of Chartrand et al. (1996) is extended by establishing the values of DOM (K n 1 , n 2 , n 3 ) for arbitrary positive integers n 1 , n 2 and n 3. While considering the orientable domination number of lexicographic product graphs, we answer in the negative a question concerning domination and packing numbers in acyclic digraphs posed in Brešar et al. (2022). [ABSTRACT FROM AUTHOR]

A vertex in a graph totally dominates another vertex if they are adjacent. A sequence of vertices in a graph G is called a total dominating sequence if every vertex v in the sequence totally dominates at least one vertex that was not totally dominated by any vertex that precedes v in the sequence, and at the end all vertices of G are totally dominated. While the length of a shortest such sequence is the total domination number of G , in this paper we investigate total dominating sequences of maximum length, which we call the Grundy total domination number, γ gr t ( G ) , of G . We provide a characterization of the graphs G for which γ gr t ( G ) = | V ( G ) | and of those for which γ gr t ( G ) = 2 . We show that if T is a nontrivial tree of order n with no vertex with two or more leaf-neighbors, then γ gr t ( T ) ≥ 2 3 ( n + 1 ) , and characterize the extremal trees. We also prove that for k ≥ 3 , if G is a connected k -regular graph of order n different from K k , k , then γ gr t ( G ) ≥ ( n + ⌈ k 2 ⌉ − 2 ) / ( k − 1 ) if G is not bipartite and γ gr t ( G ) ≥ ( n + 2 ⌈ k 2 ⌉ − 4 ) / ( k − 1 ) if G is bipartite. The Grundy total domination number is proven to be bounded from above by two times the Grundy domination number, while the former invariant can be arbitrarily smaller than the latter. Finally, a natural connection with edge covering sequences in hypergraphs is established, which in particular yields the NP-completeness of the decision version of the Grundy total domination number. [ABSTRACT FROM AUTHOR]

Motivated by the success of domination games and by a variation of the coloring game called the indicated coloring game, we introduce a version of domination games called the indicated domination game. It is played on an arbitrary graph G by two players, Dominator and Staller, where Dominator wants to finish the game in as few rounds as possible while Staller wants just the opposite. In each round, Dominator indicates a vertex u of G that has not been dominated by previous selections of Staller, which, by the rules of the game, forces Staller to select a vertex in the closed neighborhood of u. The game is finished when all vertices of G become dominated by the vertices selected by Staller. Assuming that both players are playing optimally according to their goals, the number of selected vertices during the game is the indicated domination number, γ i (G) , of G. We prove several bounds on the indicated domination number expressed in terms of other graph invariants. In particular, we find a place of the new graph invariant in the well-known domination chain, by showing that γ i (G) ≥ Γ (G) for all graphs G , and by showing that the indicated domination number is incomparable with the game domination number and also with the upper irredundance number. In connection with the trivial upper bound γ i (G) ≤ n (G) − δ (G) , we characterize the class of graphs G attaining the bound provided that n (G) ≥ 2 δ (G) + 2. We prove that in trees, split graphs and grids the indicated domination number equals the independence number. We also find a formula for the indicated domination number of powers of paths, from which we derive that there exist graphs in which the indicated domination number is arbitrarily larger than the upper irredundance number. We provide some partial results supporting the statement that γ i (G) = n (G) / 2 if G is a cubic bipartite graph, and leave this as an open question. [ABSTRACT FROM AUTHOR]

Abstract: A set of vertices in a graph is a 2-dominating set if every vertex of not in is adjacent to at least two vertices in . The 2-domination number is the minimum cardinality of a 2-dominating set in . The annihilation number is the largest integer such that the sum of the first terms of the nondecreasing degree sequence of is at most the number of edges in . The conjecture-generating computer program, Graffiti.pc, conjectured that holds for every connected graph . It is known that this conjecture is true when the minimum degree is at least 3. The conjecture remains unresolved for minimum degree 1 or 2. In this paper, we prove that the conjecture is indeed true when is a tree, and we characterize the trees that achieve equality in the bound. It is known that if is a tree on vertices with vertices of degree 1, then . As a consequence of our characterization, we also characterize trees that achieve equality in this bound. [Copyright &y& Elsevier]

Abstract: The domination game, played on a graph , was introduced in Brešar et al. (2010) [2]. Vertices are chosen, one at a time, by two players Dominator and Staller. Each chosen vertex must enlarge the set of vertices of dominated to that point in the game. Both players use an optimal strategy—Dominator plays so as to end the game as quickly as possible, and Staller plays in such a way that the game lasts as many steps as possible. The game domination number is the number of vertices chosen when Dominator starts the game and the Staller-start game domination number is the result when Staller starts the game. In this paper these two games are studied when played on trees and spanning subgraphs. A lower bound for the game domination number of a tree in terms of the order and maximum degree is proved and shown to be asymptotically tight. It is shown that for every , there is a tree with and conjectured that there is none with . A relation between the game domination number of a graph and its spanning subgraphs is considered. It is proved that there exist 3-connected graphs having a 2-connected spanning subgraph such that the game domination number of is arbitrarily smaller than that of . Similarly, for any integer , there exists a graph and a spanning tree such that . On the other hand, there exist graphs such that the game domination number of any spanning tree of is arbitrarily larger than that of . [Copyright &y& Elsevier]

Abstract: The packing chromatic number of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced. [Copyright &y& Elsevier]

Abstract: An upper bound for the domination number of the direct product of graphs is proved. It in particular implies that for any graphs G and H, . Graphs with arbitrarily large domination numbers are constructed for which this bound is attained. Concerning the upper domination number we prove that , thus confirming a conjecture from [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53–79]. Finally, for paired-domination of direct products we prove that for arbitrary graphs G and H, and also present some infinite families of graphs that attain this bound. [Copyright &y& Elsevier]

We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing's conjecture. The new framework unifies two different approaches to the conjecture. The most common approach restricts one of the factors of the product to some class of graphs and proves the inequality of the conjecture then holds when the other factor is any graph. The other approach utilizes the so-called Clark-Suen partition for proving a weaker inequality that holds for all pairs of graphs. We demonstrate the strength of our framework by improving the bound of Clark and Suen as follows: γ(X□Y) ≥ max {1/2γ (X)γt(Y), 1/2γt(X)γ(Y)}, where γ stands for the domination number, γt is the total domination number, and X □ Y is the Cartesian product of graphs X and Y [ABSTRACT FROM AUTHOR]

Abstract: This note extends results of Fernández, Leighton, and López-Presa on the uniqueness of th roots for disconnected graphs with respect to the Cartesian product to other products and shows that their methods also imply new cancelation laws. [Copyright &y& Elsevier]

If S = (a1, a2, . . .) is a non-decreasing sequence of positive integers, then an S-packing coloring of a graph G is a partition of V (G) into sets X1,X2, . . . such that for each pair of distinct vertices in the set Xi, the distance between them is larger than ai. If there exists an integer k such that V (G) = X1 ∪ · · · ∪ Xk, then the partition is called an S-packing k-coloring. The S-packing chromatic number of G is the smallest k such that G admits an S-packing k-coloring. If ai = i for every i, then the terminology reduces to packing colorings and packing chromatic number. Since the introduction of these generalizations of the chromatic number in 2008 more than fifty papers followed. Here we survey the state of the art on the packing coloring, and its generalization, the S-packing coloring. We also list several conjectures and open problems. [ABSTRACT FROM AUTHOR]

A sequence of vertices in a graph G is called a legal dominating sequence if every vertex in the sequence dominates at least one vertex not dominated by those vertices that precede it, and at the end all vertices of G are dominated. While the length of a shortest such sequence is the domination number of G , in this paper we investigate legal dominating sequences of maximum length, which we call the Grundy domination number of G . We prove that every graph has a legal dominating sequence of each possible length between its domination number and its Grundy domination number, and characterize the graphs for which the domination number and Grundy domination number are both equal to k , for k ≤ 3 . We also prove that the decision version of the Grundy domination number is NP-complete, even when restricted to the class of chordal graphs, and present linear time algorithms for determining this number in trees, cographs and split graphs. Several results are extended to the context of edge covers in hypergraphs. [ABSTRACT FROM AUTHOR]

Abstract: Two players, Dominator and Staller, alternately choose vertices of a graph , one at a time, such that each chosen vertex enlarges the set of vertices dominated so far. The aim of Dominator is to finish the game as soon as possible, while the aim of Staller is just the opposite. The game domination number is the number of vertices chosen when Dominator starts the game and both players play optimally. It has been conjectured in Kinnersley et al. (2012) [7] that holds for an arbitrary graph with no isolated vertices, which is in particular open when is a forest. In this paper, we present constructions that lead to large families of trees that attain the conjectured -bound. Some of these families can be used to construct graphs with game domination number of their order by gluing them to an arbitrary graph. All extremal trees on up to 20 vertices were found by a computer. In particular, there are exactly ten trees on 20 vertices with , all of which belong to the constructed families. [Copyright &y& Elsevier]

Abstract: We define a -limited packing in a graph, which generalizes a 2-packing in a graph, and give several bounds on the size of a -limited packing. One such bound involves the domination number of the graph, and here we show all trees attaining the bound can be built via a simple sequence of operations. We consider graphs where every maximal 2-limited packing is a maximum 2-limited packing, and characterize their structure in a number of cases. [Copyright &y& Elsevier]

Abstract: A graph G is domination bicritical if the removal of any pair of vertices decreases the domination number. Properties of bicritical graphs are studied. We show that a connected bicritical graph has domination number at least 3, minimum degree at least 3, and edge-connectivity at least 2. Ways of constructing a bicritical graph from smaller bicritical graphs are presented. [Copyright &y& Elsevier]