Decycling numbers of random regular graphs

DOI10.1002/rsa.10069zbMath1012.05099OpenAlexW2047035505MaRDI QIDQ4798175

Sheng Bau, Sanming Zhou, Nicholas C. Wormald

Publication date: 19 March 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10069

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38)

Related Items (15)

Independent domination in directed graphs ⋮ Percolation with small clusters on random graphs ⋮ Factor of IID Percolation on Trees ⋮ A new formula for the decycling number of regular graphs ⋮ Optimal segmentation of directed graph and the minimum number of feedback arcs ⋮ Hierarchical cycle-tree packing model for optimal \(K\)-core attack ⋮ Induced forests in some distance-regular graphs ⋮ Some bounds on the size of maximum G-free sets in graphs ⋮ Dismantling Sparse Random Graphs ⋮ Spin Glass approach to the feedback vertex set problem ⋮ Induced Forests in Regular Graphs with Large Girth ⋮ A spin glass approach to the directed feedback vertex set problem ⋮ On giant components and treewidth in the layers model ⋮ Cycle intersection graphs and minimum decycling sets of even graphs ⋮ Minimal contagious sets in random regular graphs

Cites Work

• Analysis of greedy algorithms on graphs with bounded degrees

This page was built for publication: Decycling numbers of random regular graphs