Verstraëte's girth-six conjecture for independent domination in cubic graphs

Let GG be a cubic graph, and let i(G)i(G) denote its independent domination number, the minimum size of an independent dominating set of GG. The girth of GG is the length of a shortest cycle in GG.

Verstraëte's conjecture. If GG is a cubic graph with girth at least 66, then

i(G)V(G)3.i(G) \leq \frac{|V(G)|}{3}.

This conjecture seeks a sharper upper bound for independent domination in cubic graphs when short cycles, and in particular the complete bipartite extremal examples, are excluded. The source gives no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon and Boram Park, “Tight bound for independent domination of cubic graphs without 4-cycles”, arXiv:2112.11720 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.