2024/01/31 by Paul Dorbec, Dorbec, Paul, Michael Antony Henning +1
Computer Science · Social Sciences · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Japanese History and Culture
paper · pdf · doi:10.48550/arxiv.2401.17820
openalex publication_date 2024/01/31 · openalex created_date 2024/02/01 · openalex updated_date 2026/07/28
A set S of vertices in a graph G is a dominating set of G if every vertex not in S is adjacent to a vertex in S . The domination number of G, denoted by γ(G), is the minimum cardinality of a dominating set in G. In a breakthrough paper in 2008, Löwenstein and Rautenbach proved that if G is a cubic graph of order n and girth at least 83, then γ(G) ≤ n/3. A natural question is if this girth condition can be lowered. The question gave birth to two 1/3-conjectures for domination in cubic graphs. The first conjecture, posed by Verstraete in 2010, states that if G is a cubic graph on n vertices with girth at least 6, then γ(G) ≤ n/3. The second conjecture, first posed as a question by Kostochka in 2009, states that if G is a cubic, bipartite graph of order n, then γ(G) ≤n/3. In this paper, 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.