Downloads

Li, L., & Yue, J. Independent Domination in Claw-Free Cubic Graphs. Applied Mathematics and Statistics. 2024. doi: Retrieved from https://test.sciltp.com/testj/ams/article/view/397
Forthcoming Issue
Copyright (c) 2024 by the authors.
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Article

Independent Domination in Claw-Free Cubic Graphs

Linyu Li 1 and Jun Yue 2,*

1 School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, China

2 School of Mathematics Science, Tiangong University, Tianjin 300387, China

* Correspondence: yuejun06@126.com

Received: 7 June 2024; Revised: 5 August 2024; Accepted: 13 August 2024; Published: 22 August 2024

 

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 -free cubic graph, then . Meanwhile,  if and only if , where is an infinite cubic family with each graph being a -necklace. Then, it is shown that if G is a -free cubic graph with no -component, then . This result is tight.

Keywords:

independent domination claw-free cubic graphs

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.