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

Kostochka A. V., Stodolsky B. Y.

DISCRETE MATHEMATICS, cilt.309, sa.5, ss.1142-1162, 2009 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 309 Sayı: 5
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1016/j.disc.2007.12.009
  • Dergi Adı: DISCRETE MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1142-1162
  • İstanbul Teknik Üniversitesi Adresli: Hayır

Özet

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.