On the independence number of random cubic graphs

We show that as n→∞, the independence number α(G), for almost all 3‐regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ϵ)n, for any constant ϵ>0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley & Sons, Inc.

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 1994-12, Vol.5 (5), p.649-664
Main Authors: Frieze, Alan, Suen, Stephen
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that as n→∞, the independence number α(G), for almost all 3‐regular graphs G on n vertices, is at least (6 log(3/2) – 2 – ϵ)n, for any constant ϵ>0. We prove this by analyzing a greedy algorithm for finding independent sets. © 1994 John Wiley & Sons, Inc.
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.3240050504