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

^*Corresponding author for this work

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

Research output: Contribution to journal › Article › peer-review

36 Citations (Scopus)

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.

Original language	English
Pages (from-to)	45-50
Number of pages	6
Journal	Discrete Mathematics
Volume	304
Issue number	1-3
DOIs	https://doi.org/10.1016/j.disc.2005.07.005
Publication status	Published - 28 Nov 2005
Externally published	Yes

Keywords

Cubic graphs
Dominating set
Domination

Access to Document

10.1016/j.disc.2005.07.005

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this