1/2-conjectures on the domination game and claw-free graphs. (March 2022)

• Record Type: Journal Article
• Authors: Bujtás, Csilla; Iršič, Vesna; Klavžar, Sandi
• Is Part Of: European journal of combinatorics. Volume 101(2022)
• Publication Date: 2022-03
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103467
• Languages: English
• ISSNs: 0195-6698

Abstract

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.