Semitotal domination in claw-free cubic graphs.

*(English)*Zbl 1386.05146W. Goddard et al. [Util. Math. 94, 67–81 (2014; Zbl 1300.05220)] introduced semitotal domination in graphs. Let \(V(G)\) be the vertex set of a graph \(G\) containing no isolated vertices. A set \(S \subseteq V(G)\) is called a semitotal dominating set of \(G\) if each vertex not in \(S\) is adjacent to a vertex in \(S\), and each vertex in \(S\) is at distance at most two from another vertex of \(S\). The semitotal domination number of \(G\), denoted by \(\gamma_{t2}(G)\), is the minimum cardinality over all semitotal dominating sets of \(G\).

For \(i\in\{1,2\}\), let \(D_i\) be a complete graph of order \(4\) minus one edge; let \(V(D_i)=\{a_i, b_i, c_i, d_i\}\) and let \(a_ib_i\) be the missing edge in \(D_i\). We denote by \(N_2\) the graph obtained from the disjoint union of \(D_1\) and \(D_2\) by adding two edges \(a_1b_2\) and \(a_2b_1\), and we denote by \(K_4\) the complete graph on \(4\) vertices.

M. A. Henning and A. J. Marcon [Ann. Comb. 20, No. 4, 799–813 (2016; Zbl 1354.05107)] showed that, if \(G\) is a connected claw-free cubic graph of order \(n \geq 10\), then \(\gamma_{t2}(G) \leq \frac{4n}{11}\), and they posed the following conjecture.

(C1) If \(G \not\in \{K_4, N_2\}\) is a connected claw-free cubic graph of order \(n\), then \(\gamma_{t2}(G) \leq \frac{n}{3}\).

In this paper, the authors prove the above conjecture (C1), and they propose the following conjecture.

(C2) If \(G \not\in \{K_4, N_2\}\) is a connected claw-free graph of order \(n\) with minimum degree at least \(3\), then \(\gamma_{t2}(G) \leq \frac{n}{3}\).

For \(i\in\{1,2\}\), let \(D_i\) be a complete graph of order \(4\) minus one edge; let \(V(D_i)=\{a_i, b_i, c_i, d_i\}\) and let \(a_ib_i\) be the missing edge in \(D_i\). We denote by \(N_2\) the graph obtained from the disjoint union of \(D_1\) and \(D_2\) by adding two edges \(a_1b_2\) and \(a_2b_1\), and we denote by \(K_4\) the complete graph on \(4\) vertices.

M. A. Henning and A. J. Marcon [Ann. Comb. 20, No. 4, 799–813 (2016; Zbl 1354.05107)] showed that, if \(G\) is a connected claw-free cubic graph of order \(n \geq 10\), then \(\gamma_{t2}(G) \leq \frac{4n}{11}\), and they posed the following conjecture.

(C1) If \(G \not\in \{K_4, N_2\}\) is a connected claw-free cubic graph of order \(n\), then \(\gamma_{t2}(G) \leq \frac{n}{3}\).

In this paper, the authors prove the above conjecture (C1), and they propose the following conjecture.

(C2) If \(G \not\in \{K_4, N_2\}\) is a connected claw-free graph of order \(n\) with minimum degree at least \(3\), then \(\gamma_{t2}(G) \leq \frac{n}{3}\).

Reviewer: Eunjeong Yi (Galveston)

##### MSC:

05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |

PDF
BibTeX
XML
Cite

\textit{E. Zhu} et al., Graphs Comb. 33, No. 5, 1119--1130 (2017; Zbl 1386.05146)

Full Text:
DOI

##### References:

[1] | Duckworth, W; Wormald, NC, Minimum independent dominating sets of random cubic graphs, Electron. J. Comb., 9, 147-161, (2002) · Zbl 1009.05106 |

[2] | Goddard, W; Henning, MA; McPillan, CA, Semitotal domination in graphs, Util. Math., 94, 67-81, (2014) · Zbl 1300.05220 |

[3] | Haas, R; Seyffarth, K, The k-dominating graph, Graph Comb., 30, 609-617, (2014) · Zbl 1294.05122 |

[4] | Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker, New York (1998) · Zbl 0883.00011 |

[5] | Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998) · Zbl 0890.05002 |

[6] | Henning, MA, A survey of selected recent results on total domination in graphs, Discrete Math., 309, 32-63, (2009) · Zbl 1219.05121 |

[7] | Henning, MA; LĂ¶wnstein, C, Locating-total domination in claw-free cubic graphs, Discrete Math., 312, 3107-3116, (2012) · Zbl 1252.05162 |

[8] | Henning, MA; Marcon, AJ, Semitotal domination in claw-free cubic graphs, Ann. Comb., 20, 1-15, (2016) · Zbl 1354.05107 |

[9] | Henning, M.A., Yeo, A.: Total Domination in Graphs. Springer, New York (2013) · Zbl 1408.05002 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.