On domination in connected cubic graphs

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

31 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 languageEnglish
Pages (from-to)45-50
Number of pages6
JournalDiscrete Mathematics
Volume304
Issue number1-3
DOIs
Publication statusPublished - 28 Nov 2005
Externally publishedYes

Keywords

  • Cubic graphs
  • Dominating set
  • Domination

Fingerprint

Dive into the research topics of 'On domination in connected cubic graphs'. Together they form a unique fingerprint.

Cite this