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

A. V. Kostochka*, B. Y. Stodolsky

*Bu çalışma için yazışmadan sorumlu yazar

Araştırma sonucu: Dergiye katkıMakalebilirkişi

20 Atıf (Scopus)

Ö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
DergiDiscrete Mathematics
Hacim309
Basın numarası5
DOI'lar
Yayın durumuYayınlandı - 28 Mar 2009
Harici olarak yayınlandıEvet

Parmak izi

An upper bound on the domination number of n-vertex connected cubic graphs' araştırma başlıklarına git. Birlikte benzersiz bir parmak izi oluştururlar.

Alıntı Yap