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

DOI10.1016/J.EJC.2021.103467MaRDI QIDQ2066003zbMATH OpenOpenAlexWikidataFDO

Authors Vesna Iršič, Sandi Klavžar, Csilla Bujtás

Publication date 13 January 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.14273

zbMATH Keywords

game domination numberline graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Games involving graphs (91A43)

Abstract: Let $gamm{a}_g(G)$ be the game domination number of a graph $G$. Rall conjectured that if $G$ is a traceable graph, then $gamm{a}_g(G)leleftlceilfrac12n(G)ightceil$. 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)geq2$, then $gamm{a}_g(G)leqleftlceilfrac12n(G)ightceil$. We show that both conjectures hold true for claw-free cubic graphs. We further prove the upper bound $gamm{a}_g(G)leleftlceilfrac1120,n(G)ightceil$ 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.

Recommendations

• On Rall's 1/2-conjecture on the domination game
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• Proof of a conjecture on game domination
• General upper bound on the game domination number
• THE DOMINATION GAME ON SPLIT GRAPHS

Cites work

• Almost all cubic graphs are Hamiltonian
• Characterisation of forests with trivial game domination numbers
• Connected domination game
• Domination game and an imagination strategy
• Domination game and minimal edge cuts
• Domination game on forests
• Domination game on paths and cycles
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• Domination game: extremal families for the 3/5-conjecture for forests
• Domination game: extremal families of graphs for \(3/5\)-conjectures
• Extremal problems for game domination number
• Game domination numbers of a disjoint union of paths and cycles
• Game total domination for cyclic bipartite graphs
• General upper bound on the game domination number
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• Maker-Breaker domination game
• On domination game stable graphs and domination game edge-critical graphs
• On Eulerian and Hamiltonian Graphs and Line Graphs
• On the game domination number of graphs with given minimum degree
• The 4/5 upper bound on the game total domination number
• THE DOMINATION GAME ON SPLIT GRAPHS
• The domination game played on unions of graphs
• The variety of domination games
• Total version of the domination game
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game

Cited in

(7)

• On Rall's 1/2-conjecture on the domination game
• Maker-Breaker total domination game on cubic graphs
• Indicated domination game
• Maker-breaker domination game on trees when Staller wins
• Optimal strategies in fractional games: vertex cover and domination
• A proof of the 3/4-conjecture for the total domination game
• Bounds on the game isolation number and exact values for paths and cycles

This page was built for publication: \( 1 / 2\)-conjectures on the domination game and claw-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2066003)