1/2-conjectures on the domination game and claw-free graphs. (March 2022) - Bujtás, Csilla; Iršič, Vesna; Klavžar, Sandi
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 ) ≤ 1 2 n ( G ) . 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 ) ≤ 1 2 n ( G ) . We show that both conjectures hold true for claw-free cubic graphs. We further prove the upper bound γ g ( G ) ≤ 11 20 n ( G ) 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.