On the connected domination number of random regular graphs

DOI10.1007/3-540-45655-4_24MaRDI QIDQ4808641zbMATH OpenFDO

Authors W. Duckworth, Bernard Mans

Publication date 12 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2387/23870210.htm

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Connected domination of regular graphs
• Minimum connected dominating sets of random cubic graphs
• Randomised algorithms for finding small weakly-connected dominating sets of regular graphs
• Small k-dominating sets of regular graphs
• On the Independent Domination Number of Random Regular Graphs

Cited in

(10)

• Connected domination of regular graphs
• A game theoretic approach for minimal connected dominating set
• Note on directed proper connection number of a random graph
• A greedy algorithm for the connected positive influence dominating set in k-regular graphs
• A new kind of domination in regular graphs
• A note on domination parameters in random graphs
• Randomised algorithms for finding small weakly-connected dominating sets of regular graphs
• Small k-dominating sets of regular graphs
• On the Distribution of the Domination Number of a New Family of Parametrized Random Digraphs
• 2-Point set domination in separable graphs

This page was built for publication: On the connected domination number of random regular graphs

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