Minimum 2-dominating sets in regular graphs

DOI10.1016/j.dam.2022.01.002zbMath1503.05093OpenAlexW4210590032MaRDI QIDQ2091810

Carlos Hoppen, Giovane Mansan

Publication date: 2 November 2022

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

Full work available at URL: https://doi.org/10.1016/j.dam.2022.01.002

zbMATH Keywords

random regular graphs2-dominationgraphs with large girth

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Properties of regular graphs with large girth via local algorithms
• A note on the k-domination number of a graph
• Connected domination of regular graphs
• Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number
• The asymptotic distribution of short cycles in random regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Analysis of greedy algorithms on graphs with bounded degrees
• Local algorithms, regular graphs of large girth, and random regular graphs
• Bounds on the 2-domination number
• Local algorithms for independent sets are half-optimal
• Suboptimality of local algorithms for a class of max-cut problems
• Asymptotic bounds on total domination in regular graphs
• On large‐girth regular graphs and random processes on trees
• On the Independent Domination Number of Random Regular Graphs
• Colouring Random 4-Regular Graphs
• Randomized greedy algorithms for finding smallk-dominating sets of regular graphs
• LATIN 2004: Theoretical Informatics

This page was built for publication: Minimum 2-dominating sets in regular graphs