Premium
Decycling numbers of random regular graphs
Author(s) -
Bau Sheng,
Wormald Nicholas C.,
Zhou Sanming
Publication year - 2002
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.10069
Subject(s) - mathematics , combinatorics , random regular graph , random graph , bounded function , discrete mathematics , regular graph , graph , cubic graph , graph power , chordal graph , line graph , voltage graph , 1 planar graph , mathematical analysis
The decycling number ϕ( G ) of a graph G is the smallest number of vertices which can be removed from G so that the resultant graph contains no cycles. In this paper, we study the decycling numbers of random regular graphs. For a random cubic graph G of order n , we prove that ϕ( G ) = ⌈ n /4 + 1/2⌉ holds asymptotically almost surely. This is the result of executing a greedy algorithm for decycling G making use of a randomly chosen Hamilton cycle. For a general random d ‐regular graph G of order n , where d ≥ 4, we prove that ϕ( G )/ n can be bounded below and above asymptotically almost surely by certain constants b ( d ) and B ( d ), depending solely on d , which are determined by solving, respectively, an algebraic equation and a system of differential equations. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 397–413, 2002