On domination in connected cubic graphs

A. V. Kostochka; B. Y. Stodolsky

doi:10.1016/j.disc.2005.07.005

On domination in connected cubic graphs

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

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

University of Illinois
RAS - Sobolev Institute of Mathematics, Siberian Branch

Araştırma sonucu: Dergiye katkı › Makale › bilirkişi

36 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 3n/8. Also, he conjectured that γ(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 γ(G)=21 and present a sequence ⌈Gk⌉k=1∞ of connected cubic graphs withlimk→∞γ(Gk)|V(Gk)|≥823=13+169.

Orijinal dil	İngilizce
Sayfa (başlangıç-bitiş)	45-50
Sayfa sayısı	6
Dergi	Discrete Mathematics
Hacim	304
Basın numarası	1-3
DOI'lar	https://doi.org/10.1016/j.disc.2005.07.005
Yayın durumu	Yayınlandı - 28 Kas 2005
Harici olarak yayınlandı	Evet

Belgeye Erişim

10.1016/j.disc.2005.07.005

Diğer Dosyalar ve Linkler

Link to publication in Scopus

Alıntı Yap

@article{d242fcb2ae8048fea936c624f0555fc5,

title = "On domination in 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 3n/8. Also, he conjectured that γ(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 γ(G)=21 and present a sequence ⌈Gk⌉k=1∞ of connected cubic graphs withlimk→∞γ(Gk)|V(Gk)|≥823=13+169.",

keywords = "Cubic graphs, Dominating set, Domination",

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

year = "2005",

month = nov,

day = "28",

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

language = "English",

volume = "304",

pages = "45--50",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - On domination in connected cubic graphs

AU - Kostochka, A. V.

AU - Stodolsky, B. Y.

PY - 2005/11/28

Y1 - 2005/11/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 3n/8. Also, he conjectured that γ(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 γ(G)=21 and present a sequence ⌈Gk⌉k=1∞ of connected cubic graphs withlimk→∞γ(Gk)|V(Gk)|≥823=13+169.

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 3n/8. Also, he conjectured that γ(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 γ(G)=21 and present a sequence ⌈Gk⌉k=1∞ of connected cubic graphs withlimk→∞γ(Gk)|V(Gk)|≥823=13+169.

KW - Cubic graphs

KW - Dominating set

KW - Domination

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

U2 - 10.1016/j.disc.2005.07.005

DO - 10.1016/j.disc.2005.07.005

M3 - Article

AN - SCOPUS:27944464584

SN - 0012-365X

VL - 304

SP - 45

EP - 50

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

On domination in connected cubic graphs

Özet

Belgeye Erişim

Diğer Dosyalar ve Linkler

Parmak izi

Alıntı Yap