Article ID Journal Published Year Pages File Type
4650020 Discrete Mathematics 2009 21 Pages PDF
Abstract

In 1996, Reed proved that the domination number γ(G)γ(G) of every nn-vertex graph GG with minimum degree at least 3 is at most 3n/83n/8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper we show that γ(G)≤4n/11γ(G)≤4n/11 for every nn-vertex cubic connected graph GG if n>8n>8. Note that Reed’s conjecture that γ(G)≤⌈n/3⌉γ(G)≤⌈n/3⌉ for every connected cubic nn-vertex graph GG is not true.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,