Premium
The dominating number of a random cubic graph
Author(s) -
Molloy Michael,
Reed Bruce
Publication year - 1995
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.3240070303
Subject(s) - combinatorics , mathematics , cubic graph , graph , discrete mathematics , random graph , voltage graph , line graph
We show that if G is a random 3‐regular graph on n vertices, then its dominating number, D(G) , almost surely satisfies .2636 n ≤ D(G) ≤ .3126 n . © 1995 John Wiley & Sons, Inc.