Özet
In 1996, Reed proved that the domination number γ (G) of every n-vertex graph G with minimum degree at least 3 is at most 3 n / 8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper we show that γ (G) ≤ 4 n / 11 for every n-vertex cubic connected graph G if n > 8. Note that Reed's conjecture that γ (G) ≤ ⌈ n / 3 ⌉ for every connected cubic n-vertex graph G is not true.
Orijinal dil | İngilizce |
---|---|
Sayfa (başlangıç-bitiş) | 1142-1162 |
Sayfa sayısı | 21 |
Dergi | Discrete Mathematics |
Hacim | 309 |
Basın numarası | 5 |
DOI'lar | |
Yayın durumu | Yayınlandı - 28 Mar 2009 |
Harici olarak yayınlandı | Evet |