Originator: Bruce Reed (or earlier?) (presented by Chris Stocker - REGS 2008)
Definitions: The domination number of a graph G, written γ(G) is the minimum size of a vertex set S such that every vertex outside S has a neighbor in S. A cubic graph is simply a 3-regular graph.
Background: We consider n-vertex graphs. In a breakthrough paper, Bruce Reed [R] proved that every cubic graph has domination number at most 3n/8. The result is sharp using graphs with 8-vertex components. Reed conjectured that every connected cubic graph has domination number at most ⌈n/3⌉. This conjecture was disproved by Kostochka and Stodolsky [KS1], who gave a sequence of connected cubic graphs with domination number asymptotic to (1/3+1/69)n. Kelmans [K] improved this, finding a sequence of graphs with domination number asymptotic to (1/3+1/60)n.
Kostochka and Stodolsky [KS2] showed that the ratio of the domination number to n cannot exceed 1/3+1/33, improving Reed's ratio of 1/3+1/24. Kostochka and Stocker [KS3] further improved the upper bound to 1/3+1/42, which equals 5/14 In REGS 2008, a connected 14-vertex graph with domination number 5 was found, but it remains open whether there are larger graphs that meet this bound.
Question: Does there exist a sequence of connected cubic graphs where the ratio of the domination number to the number of vertices in the graph tends to a value larger than 1/3+1/60?
References:
[K] Kelmans, Alexander,
Counterexamples to the cubic graph domination conjecture.
arXiv link.
[KS1] Kostochka, A. V.; Stodolsky, B. Y.
On domination in connected cubic graphs. Discrete Math. 304 (2005), no.
1-3, 45--50.
[KS2] Kostochka, A. V.; Stodolsky, B. Y.
An upper bound on the domination number of n-vertex connected cubic graphs.
[KS3] Kostochka, a. v.; Stocker, C. J.
Pre-preprint.
[R] B. Reed, Paths, stars, and the number three, Combin. Probab. Comput. 5
(1996) 277--295.