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

Abstract

Let ${\gamma }_g(G)$ be the game domination number of a graph $G$. Rall conjectured that if $G$ is a traceable graph, then ${\gamma }_g(G)\le \lceil \frac{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 $\delta (G)\ge 2$, then ${\gamma }_g(G)\le \lceil \frac{1}{2}n(G)\rceil$. We show that both conjectures hold true for claw-free cubic graphs. We further prove the upper bound ${\gamma }_g(G)\le \lceil \frac{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.

28 pages, 1 figure

References in corpus (1)

• Domination games played on line graphs of complete multipartite graphs