Article in volume
Authors:
Title:
New bounds on domination and independence in graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(3) (2023) 809-824
Received: 2020-10-29 , Revised: 2021-03-16 , Accepted: 2021-03-16 , Available online: 2021-04-21 , https://doi.org/10.7151/dmgt.2406
Abstract:
We propose new bounds on the domination number and on the independence number
of a graph and show that our bounds compare favorably to recent ones. Our bounds
are obtained by using the Bhatia-Davis inequality linking the variance,
the expected value, the minimum, and the maximum of a random variable with
bounded distribution.
Keywords:
undirected graph, domination number, independence number, bounds
References:
- N. Alon and J.H. Spencer, The Probabilistic Method (John Wiley & Sons, Inc., New York, 2008).
https://doi.org/10.1002/9780470277331 - E. Angel, R. Campigotto and C. Laforest, A new lower bound on the independence number of graphs, Discrete Appl. Math. 161 (2013) 847–852.
https://doi.org/10.1016/j.dam.2012.10.001 - R. Bhatia and C. Davis, A better bound on the variance, Amer. Math. Monthly 107 (2000) 353–357.
https://doi.org/10.1080/00029890.2000.12005203 - P.B. Borwein, On the complexity of calculating factorials, J. Algorithms 6 (1985) 376–380.
https://doi.org/10.1016/0196-6774(85)90006-9 - Y. Caro, New Results on the Independence Number (Technical Report, Tel-Aviv University, 1979).
- G.J. Chang and G.L. Nemhauser, The k-domination and k-stability Problems in sun-free chordal graphs, SIAM J. Algebraic Discrete Methods 5 (1984) 332–345.
https://doi.org/10.1137/0605034 - W.E. Clark, B. Shekhtman, S. Suen and D.C. Fisher, Upper bounds for the domination number of a graph, Congr. Numer. 132 (1998) 99–123.
- M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
- J. Harant and S. Mohr, On Selkow's bound on the independence number of graphs, Discuss. Math. Graph Theory 39 (2019) 655–657.
https://doi.org/10.7151/dmgt.2100 - J. Harant and A. Pruchnewski, A note on the domination number of a bipartite graph, Ann. Comb. 5 (2001) 175–178.
https://doi.org/10.1007/PL00001298 - J. Harant and D. Rautenbach, Domination in bipartite graphs, Discrete Math. 309 (2009) 113–122.
https://doi.org/10.1016/j.disc.2007.12.051 - J. Harant and D. Rautenbach, Independence in connected graphs, Discrete Appl. Math. 159 (2011) 79–86.
https://doi.org/10.1016/j.dam.2010.08.029 - D. Harvey and J. van der Hoeven, Integer multiplication in time O$($n log n$)$ (hal-02070778 (2019)).
en.wikipedia.org, Computational Complexity of Mathematical Operations, Arithmetic Functions - A. Schönhage, A.F.W. Grotefeld and E. Vetter, Fast algorithms –- A multitape Turing machine implementation (BI Wissenschafts-Verlag, Mannheim (1994)).
en.wikipedia.org, Computational Complexity of Mathematical Operations, Number Theory - S.M. Selkow, A probabilistic lower bound on the independence number of graphs, Discrete Math. 132 (1994) 363–365.
https://doi.org/10.1016/0012-365X(93)00102-B - V.K. Wei, A Lower Bound on the Stability Number of a Simple Graph (Technical Report 81-11217-9, Bell Laboratories, Murray Hill, NJ, 1981).
Close