Minimum independent dominating sets of random cubic graphs

DOI10.1002/rsa.10047zbMath1009.05106OpenAlexW2008704324MaRDI QIDQ4803314

Nicholas C. Wormald, William Duckworth

Publication date: 2 April 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10047

zbMATH Keywords

random greedy algorithm

Mathematics Subject Classification ID

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

Related Items (12)

Independent domination in directed graphs ⋮ Domination in Cubic Graphs of Large Girth ⋮ \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms] ⋮ Analysis of greedy algorithms on graphs with bounded degrees ⋮ The cook-book approach to the differential equation method ⋮ Semitotal domination in claw-free cubic graphs ⋮ An upper bound on the domination number of a graph with minimum degree 2 ⋮ Connected domination of regular graphs ⋮ Small maximal matchings of random cubic graphs ⋮ Domination number of cubic graphs with large girth ⋮ Minimum Power Dominating Sets of Random Cubic Graphs ⋮ Maximum induced matchings of random cubic graphs

Cites Work

• Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
• Paths, Stars and the Number Three

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