A note on independent domination in almost-regular graphs

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 School of Mathematical and Statistical Sciences, Clemson University, Clemson, USA

2 Department of Mathematics and Applied Mathematics, University of Johannesburg Auckland Park, 2006 South Africa

Abstract

A classic result in domination theory is that a regular graph has independent domination number at most half the order. We strengthen this result to ``almost-regular'' graphs by showing that if a graph has minimum degree $\delta > 0$ and maximum degree at most $\delta + 3$, and the subgraph induced by the vertices of degree $\delta + 3$ (if any) is bipartite, then the independent domination number is at most half the order. We also discuss related questions.

Keywords

Main Subjects

References

[1] A. Akbari, S. Akbari, Doosthosseini, A.Z. A.Z. Hadizadeh, M.A. Henning, and A. Naraghi, Independent domination in subcubic graphs, J. Combin. Optim. 43 (2022), 28–41.  https://doi.org/10.1007/s10878-021-00743-z
[2] E.K. Cho, I. Choi, and B. Park, On independent domination of regular graphs, J. Graph Theory 103 (2023), no. 1, 159–170. https://doi.org/10.1002/jgt.22912
[3] E.K. Cho, J. Kim, M. Kim, and S. Oum, Independent domination of graphs with bounded maximum degree, J. Combin. Theory Ser. B 158 (2023), no. 2, 341–352. https://doi.org/10.1016/j.jctb.2022.10.004
[4] E.J. Cockayne and S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math. 15 (1976), no. 3, 213–222. https://doi.org/10.1016/0012-365X(76)90026-1
[5] O. Favaron, Two relations between the parameters of independence and irredundance, Discrete Math. 70 (1988), no. 1, 17–20. https://doi.org/10.1016/0012-365X(88)90076-3
[6] W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013), no. 7, 839–854. https://doi.org/10.1016/j.disc.2012.11.031
[7] W. Goddard and M.A. Henning, Acyclic total dominating sets in cubic graphs, Appl. Anal. Discrete Math. 13 (2019), 73–84.
[8] W. Goddard, M.A. Henning, J. Lyle, and J. Southey, On the independent domination number of regular graphs, Annals Combin. 16 (2012), 719–732. https://doi.org/10.1007/s00026-012-0155-4
[9] J. Haviland, Upper bounds for independent domination in regular graphs, Discrete Math. 307 (2007), no. 21, 2643–2646. https://doi.org/10.1016/j.disc.2007.01.001
[10] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in graphs: Core concepts, Springer Monographs in Mathematics, Springer, Cham, 2023.
[11] P.C.B. Lam, W.C. Shiu, and L. Sun, On independent domination number of regular graphs, Discrete Math. 202 (1999), no. 1-3, 135–144. https://doi.org/10.1016/S0012-365X(98)00350-1
[12] C. Payan, Coverings by minimal transversals, Discrete Math. 23 (1978), no. 3, 273–277. https://doi.org/10.1016/0012-365X(78)90008-0
[13] L. Sun and J. Wang, An upper bound for the independent domination number, J. Combin. Theory Ser. B 76 (1999), no. 2, 240–246. https://doi.org/10.1006/jctb.1999.1907
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 18 April 2026

Files

Share

How to cite

Statistics