Search

Let G be a graph with vertex set V. A subset S ⊆ V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number is the minimum cardinality of a semipaired dominating set of G. We characterize the trees having a unique minimum semipaired dominating set. We also determine an upper bound on the semipaired domination number of these trees and characterize the trees attaining this bound.

In this paper we present a brief survey of bounds on selected domination parameters. We focus primarily on bounds on domination parameters in terms of the order and minimum degree of the graph. We present a list of open problems and conjectures that have yet to be solved in the hope of attracting future researchers to the field.

A set S of vertices in a graph G is a dominating set of G if every vertex not in S is adjacent to some vertex in S. The domination number, γ(G), of G is the minimum cardinality of a dominating set of G. The authors proved in [A new lower bound on the domination number of a graph, J. Comb. Optim. 38 (2019) 721–738] that if G is a connected graph of order n ≥ 2 with k ≥ 0 cycles and ℓ leaves, then γ(G) ≥ ⌈(n − ℓ + 2 − 2k)/3⌉. As a consequence of the above bound, γ(G) = (n − ℓ + 2(1 − k) + m)/3 for some integer m ≥ 0. In this paper, we characterize the class of cactus graphs achieving equality here, thereby providing a classification of all cactus graphs according to their domination number.

A set D of vertices in a graph G is a dominating set of G if every vertex outside D is adjacent in G to some vertex in D. A set D of vertices in G is a semitotal dominating set of G if D is a dominating set of G and every vertex in D is within distance 2 from another vertex of D. Given a graph G and a positive integer k, the semitotal domination problem is to decide whether G has a semitotal dominating set of cardinality at most k. The semitotal domination problem is known to be NP-complete for chordal graphs and bipartite graphs as shown in [M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theoret. Comput. Sci. 766 (2019) 46–57]. In this paper, we present a linear time algorithm to compute a minimum semitotal dominating set in block graphs. On the other hand, we show that the semitotal domination problem remains NP-complete for undirected path graphs.

A subset D ⊆ VG is a dominating set of G if every vertex in VG – D has a neighbor in D, while D is a paired-dominating set of G if D is a dominating set and the subgraph induced by D contains a perfect matching. A graph G is a DPDP -graph if it has a pair (D, P) of disjoint sets of vertices of G such that D is a dominating set and P is a paired-dominating set of G. The study of the DPDP -graphs was initiated by Southey and Henning [Cent. Eur. J. Math. 8 (2010) 459–467; J. Comb. Optim. 22 (2011) 217–234]. In this paper, we provide conditions which ensure that a graph is a DPDP -graph. In particular, we characterize the minimal DPDP -graphs.

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 γ(X□Y)≥max{12γ(X)γt(Y),12γt(X)γ(Y)}\gamma \left( {X \square Y} \right) \ge \max \left\{ {{1 \over 2}\gamma (X){\gamma _t}(Y),{1 \over 2}{\gamma _t}(X)\gamma (Y)} \right\}, where γ stands for the domination number, γt is the total domination number, and X□Y is the Cartesian product of graphs X and Y.

A self-complementary graph is a graph isomorphic to its complement. A set S of vertices in a graph G is a restrained dominating set if every vertex in V(G) \ S is adjacent to a vertex in S and to a vertex in V(G) \ S. The restrained domination number of a graph G is the minimum cardinality of a restrained dominating set of G. In this paper, we study restrained domination in self-complementary graphs. In particular, we characterize the self-complementary graphs having equal domination and restrained domination numbers.

For an integer k at least 2, and a graph G, let fk(G) be the minimum cardinality of a set X of vertices of G such that G − X has either k vertices of maximum degree or order less than k. Caro and Yuster [Discrete Mathematics 310 (2010) 742–747] conjectured that, for every k, there is a constant ck such that fk(G)≤ckn(G){f_k}\left( G \right) \le {c_k}\sqrt {n\left( G \right)} for every graph G. Verifying a conjecture of Caro, Lauri, and Zarb [arXiv:1704.08472v1], we show the best possible result that, if t is a positive integer, and F is a forest of order at most 16(t3+6t2+17t+12){1 \over 6}\left( {{t^3} + 6{t^2} + 17t + 12} \right), then f2(F ) ≤ t. We study f3(F ) for forests F in more detail obtaining similar almost tight results, and we establish upper bounds on fk(G) for graphs G of girth at least 5. For graphs G of girth more than 2p, for p at least 3, our results imply fk(G)=O(n(G)p+13p){f_k}\left( G \right) = O\left( {n{{\left( G \right)}^{{{p + 1} \over {3p}}}}} \right) . Finally, we show that, for every fixed k, and every given forest F , the value of fk(F ) can be determined in polynomial time.

A dynamic coloring of the vertices of a graph G starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. If the initial set S has the added property that it induces a subgraph of G without isolated vertices, then S is called a total forcing set in G. The minimum cardinality of a total forcing set in G is its total forcing number, denoted Ft(G). We prove that if T is a tree of order n ≥ 3 with maximum degree Δ and with n1 leaves, then n1≤Ft(T)≤1Δ((Δ-1)N+1){n_1} \le {F_t}\left( T \right) \le {1 \over \Delta }\left( {\left( {\Delta - 1} \right)N + 1} \right). In both lower and upper bounds, we characterize the infinite family of trees achieving equality. Further we show that Ft(T ) ≥ F (T ) + 1, and we characterize the extremal trees for which equality holds.

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number, i(G), of G is the minimum cardinality of an independent dominating set. Goddard and Henning [Discrete Math. 313 (2013) 839–854] posed the conjecture that if G ∉ {K3,3, C5 □ K2} is a connected, cubic graph on n vertices, then i(G)≤38n$i\left( G \right) \le {3 \over 8}n$, where C5 □ K2 is the 5-prism. As an application of known result, we observe that this conjecture is true when G is 2-connected and planar, and we provide an infinite family of such graphs that achieve the bound. We conjecture that if G is a bipartite, planar, cubic graph of order n, then i(G)≤13n$i\left( G \right) \le {1 \over 3}n$, and we provide an infinite family of such graphs that achieve this bound.

A dominating set of a graph G is a subset D ⊆ VG such that every vertex not in D is adjacent to at least one vertex in D. The cardinality of a smallest dominating set of G, denoted by γ(G), is the domination number of G. The accurate domination number of G, denoted by γa(G), is the cardinality of a smallest set D that is a dominating set of G and no |D|-element subset of VG \ D is a dominating set of G. We study graphs for which the accurate domination number is equal to the domination number. In particular, all trees G for which γa(G) = γ(G) are characterized. Furthermore, we compare the accurate domination number with the domination number of different coronas of a graph.

Let G be a graph with vertex set V and no isolated vertices. A sub-set S ⊆ V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number γpr2(G) is the minimum cardinality of a semipaired dominating set of G. We show that if G is a connected graph G of order n ≥ 3, then γpr2(G)≤23n${\gamma _{{\rm{pr}}2}}(G) \le {2 \over 3}n$, and we characterize the extremal graphs achieving equality in the bound.

A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the minimum cardinalities of a total dominating set and paired-dominating set are the total domination number, γt(G), and the paired-domination number, γpr(G), respectively. For k ≥ 2, let G be a connected k-regular graph. It is known [Schaudt, Total domination versus paired domination, Discuss. Math. Graph Theory 32 (2012) 435–447] that γpr(G)/γt(G) ≤ (2k)/(k+1). In the special case when k = 2, we observe that γpr(G)/γt(G) ≤ 4/3, with equality if and only if G ≅ C5. When k = 3, we show that γpr(G)/γt(G) ≤ 3/2, with equality if and only if G is the Petersen graph. More generally for k ≥ 2, if G has girth at least 5 and satisfies γpr(G)/γt(G) = (2k)/(k + 1), then we show that G is a diameter-2 Moore graph. As a consequence of this result, we prove that for k ≥ 2 and k ≠ 57, if G has girth at least 5, then γpr(G)/γt(G) ≤ (2k)/(k +1), with equality if and only if k = 2 and G ≅ C5 or k = 3 and G is the Petersen graph.

A dominating set in a graph G is a set S of vertices such that every vertex in V (G) \ S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.

We characterize a large subclass of the class of those graphs G for which the exponential domination number of H equals the domination number of H for every induced subgraph H of G.

In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γg(G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107] posted their 3/5-Conjecture that γg(G) ≤ ⅗n for every isolate-free forest on n vertices. Brešar, Klavžar, Košmrlj and Rall [Discrete Appl. Math. 161 (2013) 1308-1316] presented a construction that yields an infinite family of trees that attain the conjectured 3/5-bound. In this paper, we provide a much larger, but simpler, construction of extremal trees. We conjecture that if G is an isolate-free forest on n vertices satisfying γg(G) = ⅗n, then every component of G belongs to our construction.

A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating) sets is a non-dominating (non-total dominating) set partition. We show that the minimum number of sets in a non-dominating set partition of a graph G equals the total domination number of its complement G̅ and the minimum number of sets in a non-total dominating set partition of G equals the domination number of G̅ . This perspective yields new upper bounds on the domination and total domination numbers. We motivate the study of these concepts with a social network application.

Let H = (V, E) be a hypergraph with vertex set V and edge set E. A dominating set in H is a subset of vertices D ⊆ V such that for every vertex v ∈ V \ D there exists an edge e ∈ E for which v ∈ e and e ∩ D ≠ ∅. The domination number γ(H) is the minimum cardinality of a dominating set in H. It is known [Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62-71] that for k ≥ 5, if H is a hypergraph of order n and size m with all edges of size at least k and with no isolated vertex, then γ(H) ≤ (n + ⌊(k − 3)/2⌋m)/(⌊3(k − 1)/2⌋). In this paper, we apply a recent result of the authors on hypergraphs with large transversal number [M.A. Henning and C. Löwenstein, A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem, Discrete Math. 323 (2014) 69-75] to characterize the hypergraphs achieving equality in this bound.

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G), and the total domination number, γt(G). A set S of vertices in a graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt2(G), is the minimum cardinality of a semitotal dominating set of G. We observe that γ(G) ≤ γt2(G) ≤ γt(G). We characterize the set of vertices that are contained in all, or in no minimum semitotal dominating set of a tree.

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, γtd(G)$\gamma _t^d (G)$ , is the minimum cardinality of such a set. We observe that γtd(G)≤γt(G)$\gamma _t^d (G) \le \gamma _t (G)$ . A leaf of G is a vertex of degree 1, while a support vertex of G is a vertex adjacent to a leaf. We show that if T is a tree of order n with ℓ leaves and s support vertices, then 2(n−ℓ+3)/5≤γtd(T)≤(n+s−1)/2$2(n - \ell + 3)/5 \le \gamma _t^d (T) \le (n + s - 1)/2$ and we characterize the families of trees which attain these bounds. For every tree T, we show have γt(T)/γtd(T)

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.

The transversal number Τ (H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then Τ(H) < 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture. [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to some vertex in S. The total domination number, γt(G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [J. Combin. Math. Combin. Comput.58 (2006), 189–193] showed that if T is a nontrivial tree of order n, with ℓ leaves, then γt(T) ≥ (n − ℓ + 2)/2. In this paper, we first characterize all trees T of order n with ℓ leaves satisfying γt(T) = ⌈(n−ℓ+2)/2⌉. We then generalize this result to connected graphs and show that if G is a connected graph of order n ≥ 2 with k ≥ 0 cycles and ℓ leaves, then γt(G) ≥ ⌈(n − ℓ + 2)/2⌉ − k. We also characterize the graphs G achieving equality for this new bound. [ABSTRACT FROM AUTHOR]

Henning et al. (Discrete Appl Math 162:399–403, 2014) proved that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 4 11 n . In this paper, we improve the 4 11 -bound to a 5 14 -bound, and prove that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 5 14 n . [ABSTRACT FROM AUTHOR]

A subset T of vertices in a hypergraph H is a transversal if T has a nonempty intersection with every edge of H. The transversal number τ (H) of H is the minimum size of a transversal in H. A hypergraph H is 3-uniform if every edge of H has size 3. Let H be a 3-uniform hypergraph with n H vertices and m H edges. Tuza (Discrete Math 86:117–126, 1990) and Chvátal and McDiarmid (Combinatorica 12:19–26, 1992) showed that 4 τ (H) ≤ n H + m H . Chvátal and McDiarmid also showed that 6 τ (H) ≤ 2 n H + m H . The linear hypergraphs achieving equality in these bounds were characterized by the authors (Henning and Yeo in J Graph Theory 59:326–348, 2008; Discrete Math 313:959–966, 2013). In this paper, we show that these bounds can be improved if we impose some structural properties on H. We show that if H does not contain a subhypergraph isomorphic to the affine plane AG(2, 3) of order 3 with two vertices deleted, then 17 τ (H) ≤ 5 n H + 3 m H . The total domination number γ t (G) of a graph G is the minimum cardinality of a set S of vertices so that every vertex in G is adjacent to some vertex in S. It is known (Archdeacon et al. in J Graph Theory 46:207–210, 2004) that if G is a graph of order n with minimum degree at least 3, then γ t (G) ≤ 1 2 n , and that this bound is tight. As a consequence of our hypergraph results, we show that if G is a graph of order n with minimum degree at least 3 that contains no 4-cycles and no specified graph on 12 vertices as a subgraph, then γ t (G) ≤ 8 17 n . [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set. In this paper, we study the following conjecture posed by Goddard and Henning (Discrete Math. 313:839–854, 2013): If G ≇ K 3 , 3 is a connected, cubic, bipartite graph on n vertices, then i (G) ≤ 4 11 n . Henning et al. (Discrete Appl. Math. 162:399–403, 2014) prove the conjecture when the girth is at least 6. In this paper we strengthen this result by proving the conjecture when the graph has no subgraph isomorphic to K 2 , 3 . [ABSTRACT FROM AUTHOR]

In this paper, we continue our study of 2-colorings in hypergraphs (see, Henning and Yeo, 2013). A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. It is known (see Thomassen, 1992) that every 4-uniform 4-regular hypergraph is 2-colorable. Our main result in this paper is a strengthening of this result. For this purpose, we define a vertex in a hypergraph H to be a free vertex in H if we can 2-color V ( H ) ∖ { v } such that every hyperedge in H contains vertices of both colors (where v has no color). We prove that every 4-uniform 4-regular hypergraph has a free vertex. This proves a conjecture in Henning and Yeo (2015). Our proofs use a new result on not-all-equal 3-SAT which is also proved in this paper and is of interest in its own right. [ABSTRACT FROM AUTHOR]

In this paper we continue studying the independent transversal domination number in a graph, i.e., the cardinality of a smallest dominating set which intersects each maximum independent set. As our main result, we prove two upper bounds on the independent transversal domination number in terms of the order and minimum degree of a graph. [ABSTRACT FROM AUTHOR]

Abstract: For , let be a -uniform hypergraph on vertices and edges. The transversal number of is the minimum number of vertices that intersect every edge. We consider the following question: Is ? For , we show that the inequality in the question does not always hold. However, the examples we present all satisfy . A natural question is therefore whether holds when . Although we do not know the answer, we prove that the bound holds when , and for that case we characterize the hypergraphs for which equality holds. Furthermore, we prove that the bound holds when (with no restriction on the maximum degree), and again there we characterize the hypergraphs for which equality holds. Chvátal and McDiarmid [V. Chvátal, C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19–26] proved that the bound holds for (again with no restriction on the maximum degree). We characterize the extremal hypergraphs in this case. [Copyright &y& Elsevier]

Thomassen [Combinatorica, 3 (1983), pp. 393--396] proved that every digraph with minimum out-degree at least three has two vertex disjoint cycles. There are examples of 3-regular digraphs where all pairs of vertex disjoint cycles have the same length. In this paper we raise the conjectures that all 3-regular bipartite digraphs and all digraphs with minimum degree at least four have two vertex disjoint cycles of different length. We give support for our conjectures by proving that all 4-regular digraphs do indeed have two vertex disjoint cycles of different length. We furthermore discuss consequences of our results and conjectures as well as arc-weighted versions of our conjecture [ABSTRACT FROM AUTHOR]

A graph is total domination edge-critical if the addition of any edge decreases the total domination number, while a graph with minimum degree at least two is total domination vertex-critical if the removal of any vertex decreases the total domination number. A 3 EC graph is a total domination edge-critical graph with total domination number 3 and a 3 VC graph is a total domination vertex-critical graph with total domination number 3. A graph G is factor-critical if G − v has a perfect matching for every vertex v in G. In this paper, we show that every 3 EC graph of even order has a perfect matching, while every 3 EC graph of odd order with no cut-vertex is factor-critical. We also show that every 3 VC graph of even order that is K-free has a perfect matching, while every 3 VC graph of odd order that is K-free is factor-critical. We show that these results are tight in the sense that there exist 3 VC graphs of even order with no perfect matching that are K-free and 3 VC graphs of odd order that are K-free but not factor-critical. [ABSTRACT FROM AUTHOR]

Abstract: A directed dominating set in a directed graph is a set of vertices of such that every vertex has an adjacent vertex in with directed to . The directed domination number of , denoted by , is the minimum cardinality of a directed dominating set in . The directed domination number of a graph , denoted , is the maximum directed domination number over all orientations of . The directed domination number of a complete graph was first studied by Erdős [P. Erdős On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if denotes the independence number of a graph , we show that . [Copyright &y& Elsevier]

Abstract: A graph is diameter 2-critical if its diameter is 2, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order is at most and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an important association with total domination to prove the conjecture for the graphs whose complements are claw-free. [Copyright &y& Elsevier]

Abstract: A Nordhaus–Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper we continue the study of Nordhaus–Gaddum bounds for the total domination number . Let be a graph on vertices and let denote the complement of , and let denote the minimum degree among all vertices in and . For , we show that , with equality if and only if or consists of disjoint copies of . When , we improve the bounds on the sum and product of the total domination numbers of and . [Copyright &y& Elsevier]

A paired-dominating set of a graph is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph. Recently, Chen et al. (Acta Math Sci Ser A Chin Ed 27(1):166–170, 2007) proved that a cubic graph has paired-domination number at most three-fifths the number of vertices in the graph. In this paper, we show that the Petersen graph is the only connected cubic graph with paired-domination number three-fifths its order. [ABSTRACT FROM AUTHOR]

Abstract: A graph is called -critical if the removal of any vertex from the graph decreases the domination number, while a graph with no isolated vertex is -critical if the removal of any vertex that is not adjacent to a vertex of degree 1 decreases the total domination number. A -critical graph that has total domination number , is called --critical. In this paper, we introduce a class of --critical graphs of high connectivity for each integer . In particular, we provide a partial answer to the question “Which graphs are -critical and -critical or one but not the other?” posed in a recent work [W. Goddard, T.W. Haynes, M.A. Henning, L.C. van der Merwe, The diameter of total domination vertex critical graphs, Discrete Math. 286 (2004) 255–261]. [Copyright &y& Elsevier]

Let G = (V,E) be a graph and let S ⊑ V . The set S is a dominating set of G if every vertex in V \ S is adjacent to some vertex in S. The set S is a secure dominating set of G if for each u ϵ V \ S, there exists a vertex v ϵ S such that uv ϵ E and (S \ {v})∪{u} is a dominating set of G. The minimum cardinality of a secure dominating set in G is the secure domination number γs(G) of G. We show that if G is a connected graph of order n with minimum degree at least two that is not a 5-cycle, then γs(G) ≤ n/2 and this bound is sharp. Our proof uses a covering of a subset of V (G) by vertex-disjoint copies of subgraphs each of which is isomorphic to K2 or to an odd cycle. [ABSTRACT FROM AUTHOR]

Abstract: Let be a partition of the vertex set in a graph . For , let denote the least number of vertices needed in to dominate . It is known that if has order and minimum degree two, then . In this paper, we characterize those graphs of order which are edge-minimal with respect to satisfying the conditions of connected, minimum degree at least two, and . [Copyright &y& Elsevier]

Abstract: The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well known vertex covering and dominating set problems in graphs (see [T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi, M.A. Henning, Power domination in graphs applied to electrical power networks, SIAM J. Discrete Math. 15(4) (2002) 519–529]). A set of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set (following a set of rules for power system monitoring). The minimum cardinality of a power dominating set of a graph is its power domination number. In this paper, we determine the power domination number of an grid graph. [Copyright &y& Elsevier]

A setSof vertices in a graphGis a paired-dominating set ofGif every vertex ofGis adjacent to some vertex inSand if the subgraph induced byScontains a perfect matching. The minimum cardinality of a paired-dominating set ofGis the paired-domination number ofG, denoted by ?pr(G). IfGdoes not contain a graphFas an induced subgraph, thenGis said to beF-free. In particular ifF=K1,3 orK4-e, then we say thatGis claw-free or diamond-free, respectively. LetGbe a connected cubic graph of ordern. We show that (i) ifGis (K1,3,K4-e,C4)-free, then ?pr(G)=3n/8; (ii) ifGis claw-free and diamond-free, then ?pr(G)=2n/5; (iii) ifGis claw-free, then ?pr(G)=n/2. In all three cases, the extremal graphs are characterized. [ABSTRACT FROM AUTHOR]

Abstract: A set S of vertices in a graph G is a total dominating set of G if every vertex is adjacent to a vertex in S. The total domination number is the minimum cardinality of a total dominating set of G. The total domination subdivision number of a graph G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. Haynes et al. (J. Combin. Math. Combin. Comput. 44 (2003) 115) showed that for any tree T of order at least 3, . In this paper, we give a constructive characterization of trees whose total domination subdivision number is 3. [Copyright &y& Elsevier]

Abstract: A subset of vertices in a graph is a connected dominating set of if every vertex of is adjacent to a vertex in and the subgraph induced by is connected. The minimum cardinality of a connected dominating set of is the connected domination number . The girth is the length of a shortest cycle in . We show that if is a connected graph that contains at least one cycle, then , and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus–Gaddum type results. [Copyright &y& Elsevier]

A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class.) We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph rooted at some blue vertex v. The F-domination number γF(G) of a graph G is the minimum number of red vertices of G in a red–blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F rooted at v. In this paper we investigate the F-domination number for all 2-stratified graphs F of order n&les;3 rooted at a blue vertex. [Copyright &y& Elsevier]