Minimum connected dominating sets of random cubic graphs

MaRDI QIDQ5958835zbMATH OpenFDO

Authors W. Duckworth

Publication date 4 March 2002

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/121821, http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i1r7.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

connected dominating setcubic graphsrandom graph

Mathematics Subject Classification ID

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

Review text

Summary: We present a simple heuristic for finding a small connected dominating set of cubic graphs. The average-case performance of this heuristic, which is a randomised greedy algorithm, is analysed on random \(n\)-vertex cubic graphs using differential equations. In this way, we prove that the expected size of the connected dominating set returned by the algorithm is asymptotically almost surely less than \(0.5854n\).

Recommendations

• Minimum independent dominating sets of random cubic graphs
• Minimum power dominating sets of random cubic graphs
• The dominating number of a random cubic graph
• Connectivity of random cubic sum graphs
• scientific article; zbMATH DE number 125468
• Minimum connected dominating sets in finite graphs
• On domination in connected cubic graphs
• Connectivity properties of random subgraphs of the cube

Cited in

(11)

• Connected domination of regular graphs
• An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm
• scientific article; zbMATH DE number 2011847 (Why is no real title available?)
• Minimum independent dominating sets of random cubic graphs
• scientific article; zbMATH DE number 2089976 (Why is no real title available?)
• The dominating number of a random cubic graph
• Minimum power dominating sets of random cubic graphs
• scientific article; zbMATH DE number 2192085 (Why is no real title available?)
• Randomized greedy algorithms for finding smallk-dominating sets of regular graphs
• The maximum number of connected sets in regular graphs
• Minimum connected dominating sets in finite graphs

This page was built for publication: Minimum connected dominating sets of random cubic graphs

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