An upper bound on the domination number of n-vertex connected cubic graphs

Kostochka A. V., Stodolsky B. Y.

DISCRETE MATHEMATICS, vol.309, no.5, pp.1142-1162, 2009 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 309 Issue: 5
  • Publication Date: 2009
  • Doi Number: 10.1016/j.disc.2007.12.009
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.1142-1162
  • Istanbul Technical University Affiliated: No


In 1996, Reed proved that the domination number gamma(G) of every n-vertex graph G with minimum degree at least 3 is at most 3n/8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper we show that gamma(G) <= 4n/11 for every n-vertex cubic connected graph G if n > 8. Note that Reed's conjecture that gamma(G) <= inverted right perpendicularn/3inverted left perpendicular for every connected cubic n-vertex graph G is not true. (C) 2007 Elsevier B.V. All rights reserved.