On the independence number of random cubic graphs

DOI10.1002/rsa.3240050504zbMath0814.05064OpenAlexW1973072981WikidataQ57401582 ScholiaQ57401582MaRDI QIDQ4315392

Stephen Suen, Alan M. Frieze

Publication date: 11 December 1994

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

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

zbMATH Keywords

Markov chainsgreedy algorithmindependence numberrandom cubic graphs3-regular graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

On bipartization of cubic graphs by removal of an independent set ⋮ Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines ⋮ Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs ⋮ Analysis of greedy algorithms on graphs with bounded degrees ⋮ The cook-book approach to the differential equation method ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling ⋮ Large independent sets in random regular graphs

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Unnamed Item

This page was built for publication: On the independence number of random cubic graphs