ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


J. Harant

Jochen Harant

Department of MathematicsTechnical University of Ilmenau D-98684 Ilmenau GERMANY


S. Mohr

Samuel Mohr

Masaryk University



New bounds on domination and independence in graphs



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 ,


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.


undirected graph, domination number, independence number, bounds


  1. N. Alon and J.H. Spencer, The Probabilistic Method (John Wiley & Sons, Inc., New York, 2008).
  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.
  3. R. Bhatia and C. Davis, A better bound on the variance, Amer. Math. Monthly 107 (2000) 353–357.
  4. P.B. Borwein, On the complexity of calculating factorials, J. Algorithms 6 (1985) 376–380.
  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.
  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.
  10. J. Harant and A. Pruchnewski, A note on the domination number of a bipartite graph, Ann. Comb. 5 (2001) 175–178.
  11. J. Harant and D. Rautenbach, Domination in bipartite graphs, Discrete Math. 309 (2009) 113–122.
  12. J. Harant and D. Rautenbach, Independence in connected graphs, Discrete Appl. Math. 159 (2011) 79–86.
  13. D. Harvey and J. van der Hoeven, Integer multiplication in time O$($n log n$)$ (hal-02070778 (2019))., 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))., 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.
  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).