Domination versus total domination in claw-free cubic graphs

A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, every vertex in S is adjacent to some other vertex in S, then S is a total dominating set. The domination number $\gamma (G)$ of G is the minimum cardinality of a dominating set in G, while the total domination number ${\gamma }_t(G)$ of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain $K_{1,3}$ as an induced subgraph. Let G be a connected, claw-free, cubic graph of order n. We show that if we exclude two graphs, then $\frac{{\gamma }_t(G)}{\gamma (G)}\le \frac{12}{7}$, and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then ${\gamma }_t(G)\le \frac{3}{7}n$, and this bound is best possible. These bounds improve previously best known results due to Favaron and Henning (2008) [7], Southey and Henning (2010) [19].     

Upper minus domination in a claw-free cubic graph

We show in this paper that the upper minus domination number Γ^-(G) of a claw-free cubic graph G is at most .     

Counting labeled claw-free cubic graphs by connectivity

Claw-free cubic graphs are counted with given connectedness and order. Tables are provided for claw-free cubic graphs with given connectedness. This builds on methods for counting general cubic graphs by connectivity previously developed by Chae, Palmer, and Robinson, and on the earlier enumeration of all claw-free cubic graphs by McKay, Palmer, Read, and Robinson.     

Properties of total domination edge-critical graphs

A set S of vertices in a graph G is a total dominating set of G 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 γ_t(G) of G. The graph G is total domination edge critical if for every edge e in the complement of G, γ_t(G+e)<γ_t(G). We call such graphs γ_tEC. Properties of γ_tEC graphs are established.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

The asymptotic number of claw-free cubic graphs

Let H_n be the number of claw-free cubic graphs on 2n labeled nodes. In an earlier paper we characterized claw-free cubic graphs and derived a recurrence relation for H_n. Here we determine the asymptotic behavior of this sequence:

     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the 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. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

Bounds on total domination in claw-free cubic graphs

A set S of vertices in a graph G is a total dominating set, denoted by TDS, of G if every vertex of G is adjacent to some vertex in S (other than itself). The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_t(G). If G does not contain K_1,3 as an induced subgraph, then G is said to be claw-free. It is shown in [D. Archdeacon, J. Ellis-Monaghan, D. Fischer, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004) 207-210.] that if G is a graph of order n with minimum degree at least three, then γ_t(G)?n/2. Two infinite families of connected cubic graphs with total domination number one-half their orders are constructed in [O. Favaron, M.A. Henning, C.M. Mynhardt, J. Puech, Total domination in graphs with minimum degree three, J. Graph Theory 34(1) (2000) 9-19.] which shows that this bound of n/2 is sharp. However, every graph in these two families, except for K₄ and a cubic graph of order eight, contains a claw. It is therefore a natural question to ask whether this upper bound of n/2 can be improved if we restrict G to be a connected cubic claw-free graph of order at least 10. In this paper, we answer this question in the affirmative. We prove that if G is a connected claw-free cubic graph of order n?10, then γ_t(G)?5n/11.     

A survey of selected recent results on total domination in graphs

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. In this paper, we offer a survey of selected recent results on total domination in graphs.     

On the total domination number of cross products of graphs

We give lower and upper bounds on the total domination number of the cross product of two graphs, γ_t(G×H). These bounds are in terms of the total domination number and the maximum degree of the factors and are best possible. We further investigate cross products involving paths and cycles. We determine the exact values of γ_t(G×Pn) and γ_t(C_n×C_m) where P_n and C_n denote, respectively, a path and a cycle of length n.     

Simultaneous graph parameters: Factor domination and factor total domination

Let F₁,F₂,…,F_k be graphs with the same vertex set V. A subset S⊆V is a factor dominating set if in every F_i every vertex not in S is adjacent to a vertex in S, and a factor total dominating set if in every F_i every vertex in V is adjacent to a vertex in S. The cardinality of a smallest such set is the factor (total) domination number. In this note, we investigate bounds on the factor (total) domination number. These bounds exploit results on colorings of graphs and transversals of hypergraphs.     

On the number of components in 2-factors of claw-free graphs

In this paper, we prove that if a claw-free graph G with minimum degree δ?4 has no maximal clique of two vertices, then G has a 2-factor with at most (|G|-1)/4 components. This upper bound is best possible. Additionally, we give a family of claw-free graphs with minimum degree δ?4 in which every 2-factor contains more than n/δ components.     

Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213–229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002) 1–25] showed that there is a unique planar graph of diameter two with domination number three. It follows that the total domination number of a planar graph of diameter two is at most three. In this paper, we consider the problem of characterizing planar graphs with diameter two and total domination number three. We say that a graph satisfies the domination-cycle property if there is some minimum dominating set of the graph not contained in any induced 5-cycle. We characterize the planar graphs with diameter two and total domination number three that satisfy the domination-cycle property and show that there are exactly thirty-four such planar graphs.     

Bounds relating the weakly connected domination number to the total domination number and the matching number

Let G=(V,E) be a connected graph. A dominating set S of G is a weakly connected dominating set of G if the subgraph (V,E∩(S×V)) of G with vertex set V that consists of all edges of G incident with at least one vertex of S is connected. The minimum cardinality of a weakly connected dominating set of G is the weakly connected domination number, denoted . A set S of vertices in G is a total dominating set of G 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 γ_t(G) of G. In this paper, we show that . Properties of connected graphs that achieve equality in these bounds are presented. We characterize bipartite graphs as well as the family of graphs of large girth that achieve equality in the lower bound, and we characterize the trees achieving equality in the upper bound. The number of edges in a maximum matching of G is called the matching number of G, denoted α^′(G). We also establish that , and show that for every tree T.     

On total domination vertex critical graphs of high connectivity

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 γ_t-critical if the removal of any vertex that is not adjacent to a vertex of degree 1 decreases the total domination number. A γ_t-critical graph that has total domination number k, is called k-γ_t-critical. In this paper, we introduce a class of k-γ_t-critical graphs of high connectivity for each integer k≥3. In particular, we provide a partial answer to the question “Which graphs are γ-critical and γ_t-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].