The 3/5-conjecture for weakly S(K₁, 3)-free forests

DOI10.1016/J.DISC.2016.05.017MaRDI QIDQ2629288zbMATH OpenOpenAlexWikidataFDO

Authors Simon Schmidt

Publication date 5 July 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

3 / 5-conjecturedomination game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games involving graphs (91A43)

Abstract: The $3/5$-conjecture for the domination game states that the game domination numbers of an isolate-free graph $G$ on $n$ vertices are bounded as follows: $gamm{a}_g(G)leqfrac3n5$ and $gamm{a_g}^{\prime }(G)leqfrac3n+25$. Recent progress have been done on the subject and the conjecture is now proved for graphs with minimum degree at least $2$. One powerful tool, introduced by Bujt'as is the so-called greedy strategy for D. In particular, using this strategy, she has proved the conjecture for isolate-free forests without leafs at distance $4$. In this paper, we improve this strategy to extend the result to the larger class of weakly $S(K_{1,3})$-free forests, where a weakly $S(K_{1,3})$-free forest $F$ is an isolate-free forest without induced $S(K_{1,3})$, whose leafs are leafs of $F$ as well.

Recommendations

• Domination game: extremal families for the 3/5-conjecture for forests
• Domination game: extremal families of graphs for \(3/5\)-conjectures
• General upper bound on the game domination number
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• Domination game on forests

Cites work

• Characterisation of forests with trivial game domination numbers
• Domination game and an imagination strategy
• Domination game on forests
• Domination game played on trees and spanning subgraphs
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• Domination game: effect of edge- and vertex-removal
• Domination game: extremal families of graphs for \(3/5\)-conjectures
• Extremal problems for game domination number
• On the game domination number of graphs with given minimum degree
• Realizations of the game domination number
• The domination game played on unions of graphs
• Total version of the domination game

Cited in

(20)

• Infinite families of circular and Möbius ladders that are total domination game critical
• Domination game and minimal edge cuts
• Cutting lemma and union lemma for the domination game
• Domination game on uniform hypergraphs
• Bounds on the 2-domination number
• On graphs with largest possible game domination number
• Game total domination critical graphs
• The variety of domination games
• Fast winning strategies for the maker-breaker domination game
• General upper bound on the game domination number
• Maker-breaker domination number
• Fractional domination game
• Complexity of the game domination problem
• An introduction to game domination in graphs
• Mycielskian of graphs with small game domination number
• The enclaveless competition game
• Domination game: extremal families for the 3/5-conjecture for forests
• A proof of the 3/5-conjecture in the domination game
• A proof of the 3/4-conjecture for the total domination game
• Domination game: effect of edge contraction and edge subdivision

This page was built for publication: The 3/5-conjecture for weakly \(S(K_{1, 3})\)-free forests

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