Independent Domination in Claw-Free Cubic Graphs

Linyu Li; Jun Yue

doi:10.53941/ams.2024.100003

Abstract

A vertex set S of a graph G is called an independent dominating set if S is an independent set and each vertex in V(G)\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 in G. This paper first proves that if G is a connected \(K_{1,3}\)-free cubic graph, then \(i(G)\leq \frac{1}{3}|V(G)|\). Meanwhile, \(i(G)=\frac{1}{3}|V(G)|\) if and only if \(G\in \mathcal{H}\), where \(\mathcal{H}\) is an infinite cubic family with each graph being a \(C_6^+\)-necklace. Then, it is shown that if G is a \(\{K_{1,3}, K_4^-, C_6^+\}\)-free cubic graph with no \(C_3\Box K_2\)-component, then \(i(G)\leq \frac{5}{18}|V(G)|\). This result is tight.

References

1.
Haynes, T.W.; Hedetniemi, S.T.; Henning, M.A. (Eds.) Topics in Domination in Graphs; Developments in Mathematics. Springer: Cham, Switzerland, 2020; Volume 64.
2.
Haynes, T.W.; Hedetniemi, S.T.; Henning, M.A. (Eds.) Structures of Domination in Graphs; Developments in Mathematics. Springer: Cham, Switzerland, 2021; Volume 66.
3.
Goddard, W.; Henning, M.A. Independent domination in graphs: A survey and recent results. Discrete Math. 2013, 313, 839–854.
4.
Faudree, R.; Flandrin, E.; Ryjacek, Z. Claw-free graphs-a survey. Discrete Math. 1997, 164, 87–147.
5.
Goddard, W.; Henning, M.A.; Lyle, J.; Souyhey, J. On the independent domination number of regular graphs. Ann. Combin. 2012, 16, 719–732.
6.
Goddard, W.; Lyle, J. Independent dominating sets in triangle-free graphs. J. Combin. Optim. 2012, 23, 9–20.
7.
Henning, M.A.; Lowenstein, C.; Rautenbach, D. Independent domination in subcubic bipartite graphs of girth at least six. Discrete Appl. Math. 2014, 162, 399–402.
8.
Southey, J.; Henning, M.A. Domination versus independent domination in cubic graphs. Discrete Math. 2013, 313, 1212–1220.
9.
Rosenfeld, M. Independent sets in regular graphs. Israek J. Math. 1964, 2, 262–272.
10.
Lam, P.C.B.; Shiu, W.C.; Sun, L. On independent domination number of regular graphs. Discrete Math. 1999, 202, 135–144.
11.
Dorbec, P.; Henning, M.A. Independent domination in cubic graphs. J. Graph Theory 2015, 80, 329–349.
12.
Murugesan, N.; Nair, D.S. The domination and indepedence of some cubic bipartite graphs. Int. J. Contemp. Math. Sci. 2011, 6, 611–618.
13.
Wang, C. Independent number in claw-free cubic graphs. Acta Math. Sci. 2009, 29, 145–150.

Scilight Press

Author Information

Abstract

Keywords

References

About Scilight

Journals

Publishing Policies

Contact Us