Asymptotic bounds on total domination in regular graphs

DOI10.1016/j.disc.2020.112287zbMath1460.05146arXiv1812.03560OpenAlexW3120080034MaRDI QIDQ2659200

Giovane Mansan, Carlos Hoppen

Publication date: 25 March 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

total dominationrandom regular graphlarge girth

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Minimum 2-dominating sets in regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Properties of regular graphs with large girth via local algorithms
• The cook-book approach to the differential equation method
• Total domination of graphs and small transversals of hypergraphs
• Total domination in graphs with given girth
• The asymptotic distribution of short cycles in random regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• Local algorithms, regular graphs of large girth, and random regular graphs
• Local algorithms for independent sets are half-optimal
• Total domination in regular graphs
• Suboptimality of local algorithms for a class of max-cut problems
• Transversals in 5-uniform hypergraphs and total domination in graphs with minimum degree five
• Graph Theory and Probability
• Total domination in graphs
• Some remarks on domination
• Graphs with large total domination number
• Total Domination in Graphs
• On large‐girth regular graphs and random processes on trees
• Reducibility among Combinatorial Problems
• On the Independent Domination Number of Random Regular Graphs
• Randomized greedy algorithms for finding smallk-dominating sets of regular graphs
• Limits of local algorithms over sparse random graphs