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

A. V. Kostochka; B. Y. Stodolsky

doi:10.1016/j.disc.2007.12.009

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ı › Makale › bilirkişi

24 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
Dergi	Discrete Mathematics
Hacim	309
Basın numarası	5
DOI'lar	https://doi.org/10.1016/j.disc.2007.12.009
Yayın durumu	Yayınlandı - 28 Mar 2009
Harici olarak yayınlandı	Evet

Finansman

The first author was supported in part by NSF grants DMS-0400498 and DMS-0650784 and grants 05-01-00816 and 06-01-00694 of the Russian Foundation for Basic Research.

Finansörler	Finansör numarası
National Science Foundation	DMS-0400498, DMS-0650784, 05-01-00816, 06-01-00694
Russian Foundation for Basic Research

Belgeye Erişim

10.1016/j.disc.2007.12.009

Diğer Dosyalar ve Linkler

Link to publication in Scopus

Alıntı Yap

@article{67a27208ed3a41ada5330eea77732b2f,

title = "An upper bound on the domination number of n-vertex connected cubic graphs",

abstract = "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.",

keywords = "Connected graphs, Cubic graphs, Domination",

author = "Kostochka, \{A. V.\} and Stodolsky, \{B. Y.\}",

year = "2009",

month = mar,

day = "28",

doi = "10.1016/j.disc.2007.12.009",

language = "English",

volume = "309",

pages = "1142--1162",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

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

AU - Kostochka, A. V.

AU - Stodolsky, B. Y.

PY - 2009/3/28

Y1 - 2009/3/28

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

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

KW - Connected graphs

KW - Cubic graphs

KW - Domination

UR - https://www.scopus.com/pages/publications/60549101735

U2 - 10.1016/j.disc.2007.12.009

DO - 10.1016/j.disc.2007.12.009

M3 - Article

AN - SCOPUS:60549101735

SN - 0012-365X

VL - 309

SP - 1142

EP - 1162

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

ER -

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

Özet

Finansman

Belgeye Erişim

Diğer Dosyalar ve Linkler

Parmak izi

Alıntı Yap