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 | |
Publication status | Published - 28 Nov 2005 |
Externally published | Yes |
Keywords
- Cubic graphs
- Dominating set
- Domination