Premium
On the independence number of random cubic graphs
Author(s) -
Frieze Alan,
Suen Stephen
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050504
Subject(s) - independence number , combinatorics , independence (probability theory) , mathematics , constant (computer programming) , discrete mathematics , random graph , cubic graph , graph , computer science , statistics , line graph , programming language , voltage graph
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom