1/2-conjectures on the domination game and claw-free graphs

2020/10/27 by Csilla Bujtás, Bujtás, Csilla, Vesna Iršič +3 · 1 citation
Computer Science · #05C57 #05C69 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2010.14273

openalex publication_date 2020/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

Let γ_g(G) be the game domination number of a graph G. Rall conjectured that if G is a traceable graph, then γ_g(G) ≤ \lceil (1)/(2)n(G)\rceil. Our main result verifies the conjecture over the class of line graphs. Moreover, in this paper we put forward the conjecture that if δ(G) ≥ 2, then γ_g(G) ≤ \lceil (1)/(2)n(G) \rceil. We show that both conjectures hold true for claw-free cubic graphs. We further prove the upper bound γ_g(G) ≤ \lceil (11)/(20) n(G) \rceil over the class of claw-free graphs of minimum degree at least 2. Computer experiments supporting the new conjecture and sharpness examples are also presented.

Citations

• The domination game played on diameter 2 graphs

Cited by

• Bounds on the game isolation number and exact values for paths and cycles

Related

• On Rall's 1/2-conjecture on the domination game
• Domination versus edge domination
• Domination game and minimal edge cuts
• On the game domination number of graphs with given minimum degree
• The domination game played on diameter 2 graphs