The 13‐Conjectures for Domination in Cubic Graphs

A set of vertices in a graph is a dominating set of if every vertex not in is adjacent to a vertex in . The domination number of , denoted by , is the minimum cardinality among all dominating sets in . In a breakthrough paper in 2008, Löwenstein and Rautenbach proved that if is a cubic graph of order and girth at least 83, then . A natural question is if this girth condition can be lowered. The question gave birth to two ‐conjectures for domination in cubic graphs. The first conjecture, posed by Verstraete in 2010, states that if is a cubic graph on vertices with girth at least 6, then . The second conjecture, first posed as a question by Kostochka in 2009, states that if is a cubic, bipartite graph of order , then . In this article, we prove Verstraete's conjecture when there is no 7‐cycle and no 8‐cycle, and we prove the Kostochka's related conjecture for bipartite graphs when there is no 4‐cycle and no 8‐cycle.