Counterexamples to the Cubic Graph Domination Conjecture

Abstract

Let v(G) and dom(G) denote the number of vertices and the domination number of a graph G, and let r (G) = dom(G)/v(G)$.Let[x]and]x[bethefloorandtheceilingofanumberx.In1996B.ReedconjecturedthatifGisacubicgraph,thendom(G)isatmost]v(G)/3[.In2005A.KostochkaandB.Stodolskydisprovedthisconjectureforcubicgraphsofconnectivityoneandmaintainedthattheconjecturemaystillbetruefor2-connectedcubicgraphs.TheirminimumcounterexampleChas4bridges,v(C)=60,anddom(C)=21.InthispaperwedisproveRee{d}^{\prime }sconjecturefor2-connectedcubicgraphsbyprovidingasequence(R(k):k>2)ofcubicgraphsofconnectivitytwowithr(R_k)=1/3+1/60,wherev(R(k+1))>v(R(k))>v(R(3))=60fork>3,andsodom(R(3))=21$ and dom(R(k)) - ]v(R(k))/3[ tends to infinity when k tends to infinity. We also provide a sequence of (L_s: s > 0) of cubic graphs of connectivity one with r(L(s)) > 1/3 + 1/60. The minimum counterexample L = L(1) in this sequence is `better' than C in the sense that L has 2 bridges while C has 4 bridges, v(L) = 54 < 60 = v(C), and r(L) = 1/3 + 1/54} > 1/3 + 1/60 = r(C). We also give a construction providing for every t in {0,1,2} infinitely many cubic cyclically 4-connected Hamiltonian graphs G(t) such that v(G(t)) = t mod 3, t in {0,2} implies dom(G(t)) = ]v(G(r))/3[, and t = 1 implies dom(G(t)) = [v(G(r))/3]. At last we suggest a stronger conjecture on domination in cubic 3-connected graphs.

8 pages

Cited by in corpus (2)

• Packing 3-Vertex Paths in Claw-Free Graphs
• Packing 3-vertex paths in cubic 3-connected graphs