Geodesic
New bounds on domination and independence in graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 809-824 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 
@article{DMGT_2023_43_3_a14,
     author = {Harant, Jochen and Mohr, Samuel},
     title = {New bounds on domination and independence in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {809--824},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a14/}
}
TY  - JOUR
AU  - Harant, Jochen
AU  - Mohr, Samuel
TI  - New bounds on domination and independence in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 809
EP  - 824
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a14/
LA  - en
ID  - DMGT_2023_43_3_a14
ER  - 
%0 Journal Article
%A Harant, Jochen
%A Mohr, Samuel
%T New bounds on domination and independence in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 809-824
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a14/
%G en
%F DMGT_2023_43_3_a14
Harant, Jochen; Mohr, Samuel. New bounds on domination and independence in graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 809-824. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a14/

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

[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.001

[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.12005203

[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-9

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

[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/0605034

[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.

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

[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.2100

[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/PL00001298

[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.051

[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.029

[13] 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

[14] 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

[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-B

[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).