1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

New Bounds on Domination and Independence in Graphs1

Published Online: 17 Jun 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 29 Oct 2020
Accepted: 16 Mar 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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

MSC 2010

[1] N. Alon and J.H. Spencer, The Probabilistic Method (John Wiley & Sons, Inc., New York, 2008). https://doi.org/10.1002/978047027733110.1002/9780470277331Search in Google Scholar

[2] 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.00110.1016/j.dam.2012.10.001Search in Google Scholar

[3] 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.1200520310.1080/00029890.2000.12005203Search in Google Scholar

[4] P.B. Borwein, On the complexity of calculating factorials, J. Algorithms 6 (1985) 376–380. https://doi.org/10.1016/0196-6774(85)90006-910.1016/0196-6774(85)90006-9Search in Google Scholar

[5] Y. Caro, New Results on the Independence Number (Technical Report, Tel-Aviv University, 1979).Search in Google Scholar

[6] 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/060503410.1137/0605034Search in Google Scholar

[7] 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.Search in Google Scholar

[8] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).Search in Google Scholar

[9] 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.210010.7151/dmgt.2100Search in Google Scholar

[10] 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/PL0000129810.1007/PL00001298Search in Google Scholar

[11] J. Harant and D. Rautenbach, Domination in bipartite graphs, Discrete Math. 309 (2009) 113–122. https://doi.org/10.1016/j.disc.2007.12.05110.1016/j.disc.2007.12.051Search in Google Scholar

[12] 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.02910.1016/j.dam.2010.08.029Search in Google Scholar

[13] D. Harvey and J. van der Hoeven, Integer multiplication in time O(n log n) (hal-02070778 (2019)). see also: en.wikipedia.org, Computational Complexity of Mathematical Operations, Arithmetic Functions.Search in Google Scholar

[14] A. Schönhage, A.F.W. Grotefeld and E. Vetter, Fast algorithms — A multitape Turing machine implementation (BI Wissenschafts-Verlag, Mannheim (1994)). see also: en.wikipedia.org, Computational Complexity of Mathematical Operations, Number Theory.Search in Google Scholar

[15] 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-B10.1016/0012-365X(93)00102-BSearch in Google Scholar

[16] 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).Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo