Independent domination, order, size, and maximum degree

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 Instituto de Matemática e EstatÍstica, Universidade Federal Fluminense, Niterói, Brazil

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

3 Institute of Optimization and Operations Research, Ulm University, Ulm, Germany

Abstract

For a connected graph $G$ with $n>2\Delta$ vertices, $m$ edges, and maximum degree at most $\Delta\geq 3$, we show $i(G)\leq \left(1-\Omega\left(\frac{1}{\Delta^4}\right)\right)n-\frac{m}{\Delta}+O\left(\frac{1}{\Delta^2}\right)$ and discuss related problems.  

Keywords

Main Subjects

References

[1] C. Berge, The Theory of Graphs and Its Applications, John Wiley & Sons, Inc., New York, 1962.
[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. Comb. Theory, Ser. B 158 (2023), 341–352. https://doi.org/10.1016/j.jctb.2022.10.004
[4] E.K. Cho and M. Kim, Independent domination versus packing in subcubic graphs, Discrete Appl. Math. 357 (2024), 132–134. https://doi.org/10.1016/j.dam.2024.06.007
[5] E.J. Cockayne, O. Favaron, H. Li, and G. MacGillivray, The product of the independent domination numbers of a graph and its complement, Discrete Math. 90 (1991), no. 3, 313–317. https://doi.org/10.1016/0012-365X(91)90151-Q
[6] E.J. Cockayne, O. Favaron, C. Payan, and A.G. Thomason, Contributions to the theory of domination, independence and irredundance in graphs, Discrete Math. 33 (1981), no. 3, 249–258. https://doi.org/10.1016/0012-365X(81)90268-5
[7] E.J. Cockayne and S.T. Hedetniemi, Independence graphs, Cong. Numer. 10 (1974), 471–491.
[8] P. Dankelmann, G.S. Domke, W. Goddard, P. Grobler, J.H. Hattingh, and H.C. Swart, Maximum sizes of graphs with given domination parameters, Discrete Math. 281 (2004), no. 1-3, 137–148. https://doi.org/10.1016/j.disc.2003.07.010
[9] P. Erdös and P. Kelly, The minimal regular graph containing a given graph, A Seminar on Graph Theory, Holt, Rinehart and Winston, New York-Toronto, 1967, pp. 65–69.
[10] O. Favaron, On a conjecture of fink and jacobson concerning $k$-domination and $k$-dependence, J. Comb. Theory, Ser. B 39 (1985), no. 1, 101–102. https://doi.org/10.1016/0095-8956(85)90040-1
[11] O. Favaron, Stability, domination and irredundance in a graph, J. Graph Theory 10 (1986), no. 4, 429–438. https://doi.org/10.1002/jgt.3190100402
[12] O. Favaron,$ $k-domination and $k$-independence in graphs, Ars Combin. 25 (1988), 159–167.
[13] 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
[14] O. Favaron, A bound on the independent domination number of a tree, Vishwa Internat. J. Graph Theory 1 (1992), 19–27.
[15] O. Favaron, Global alliances and independent domination in some classes of graphs, Electron. J. Comb. 15 (2008), Article number: R123. https://doi.org/10.37236/847
[16] O. Favaron, T.W. Haynes, and P.J. Slater, Distance-$k$ independent domination sequences, J. Comb. Math. Comb. Comput. 33 (2000), 225–237.
[17] 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
[18] J. Haviland, On independent domination and size, Australas. J. Comb. 42 (2008), 279–284.
[19] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, Springer, 2023.
[20] 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
[21] O. Ore, Theory of Graphs, American Math. Soc., 1962.
[22] M. Rosenfeld, Independent sets in regular graphs, Isr. J. Math. 2 (1964), no. 4, 262–272. https://doi.org/10.1007/BF02759743
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 04 November 2025

Files

Share

How to cite

Statistics