zbMATH — the first resource for mathematics

Decycling numbers of random regular graphs. (English) Zbl 1012.05099
Summary: The decycling number \(\phi(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 \(\phi (G) = \lceil n/4 + 1/2\rceil\) 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\geq 4\), we prove that \(\phi (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.

05C38 Paths and cycles
05C80 Random graphs (graph-theoretic aspects)
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Alon, J Graph Theory 38 pp 113– (2001)
[2] Bafna, SIAM J Discrete Math 12 pp 289– (1999)
[3] Bau, Austr J Combinat 25 pp 285– (2002)
[4] Bau, Utilitas Math 59 pp 129– (2001)
[5] Beineke, J Graph Theory 25 pp 59– (1997)
[6] Random graphs, Academic Press, London, 1985.
[7] Bondy, Can Math Bull 30 pp 193– (1987)
[8] Britikov, Mat Zametki 43 pp 672– (1988)
[9] Graph theory, Springer-Verlag, New York, 1997.
[10] Duckworth, Random Struct Alg
[11] Erd?s, J Combinat Theory 41B pp 61– (1986)
[12] ?Reducibility among combinatorial problems,? Complexity of computer computations, Eds. and 85-103, Plenum Press, New York, London, 1972.
[13] Kim, J Combinat Theory Ser B 81 pp 20– (2001)
[14] Kirchhoff, Ann Phys Chem 72 pp 497– (1847)
[15] Li, Acta Math Sci (Engl Ed) 19 pp 375– (1999)
[16] Liang, Inf Process Lett 52 pp 123– (1994)
[17] Liang, Acta Inf 34 pp 337– (1997)
[18] Liu, Discrete Math 148 pp 119– (1996)
[19] ?Concentration,? Probabilistic methods for algorithmic discrete mathematics, Eds. et al., 195-248, Springer-Verlag, Berlin, 1998.
[20] ?Asymptotic enumeration methods,? Handbook of Combinatorics, Vol. II, Eds. and Elsevier, Amsterdam, 1995.
[21] Robinson, Random Struct Alg 3 pp 117– (1992)
[22] Robinson, Random Struct Alg 5 pp 363– (1994)
[23] Ruci?ski, J Austr Math Soc 72 pp 67– (2002)
[24] Ueno, Discrete Math 72 pp 355– (1988)
[25] Wormald, Ann Appl Probab 5 pp 1217– (1995)
[26] ?The differential equation method for random graph processes and greedy algorithms,? Lectures on approximation and randomized algorithms, Eds. and 73-155. PWN, Warsaw, 1999.
[27] ?Models of random regular graphs,? Surveys in combinatorics, 1999, Eds. and London Mathematical Society Lecture Notes Series, Vol. 267, 239-298. Cambridge University Press, Cambridge, 1999.
[28] Analysis of greedy algorithms on graphs with bounded degrees, Discrete Math, to appear. · Zbl 1029.05147
[29] Zheng, Discrete Math 85 pp 89– (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.