On domination in connected cubic graphs

Kostochka A., Stodolsky B. Y.

DISCRETE MATHEMATICS, cilt.304, ss.45-50, 2005 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 304
  • Basım Tarihi: 2005
  • Doi Numarası: 10.1016/j.disc.2005.07.005
  • Dergi Adı: DISCRETE MATHEMATICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.45-50
  • İ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. Also, he conjectured that gamma(H) <= [n/3] for every connected 3-regular (cubic) n-vertex graph H. In this note, we disprove this conjecture. We construct a connected cubic graph G on 60 vertices with gamma(G) = 21 and present a sequence {G(k)}(k=1)(infinity) of connected cubic graphs with lim(k ->infinity) gamma(G(k))/vertical bar V(G(k))vertical bar >= 8/23 = 1/3 + 1/69. (c) 2005 Elsevier B.V. All rights reserved.