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


Kostochka A. V. , Stodolsky B. Y.

DISCRETE MATHEMATICS, cilt.309, ss.1142-1162, 2009 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 309 Konu: 5
  • Basım Tarihi: 2009
  • Doi Numarası: 10.1016/j.disc.2007.12.009
  • Dergi Adı: DISCRETE MATHEMATICS
  • Sayfa Sayıları: ss.1142-1162

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