Induced Forests in Regular Graphs with Large Girth

DOI10.1017/S0963548307008905zbMath1185.05040arXiv0709.3126MaRDI QIDQ3545905

Carlos Hoppen, Nicholas C. Wormald

Publication date: 11 December 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0709.3126

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12)

Related Items

Percolation with small clusters on random graphs, Factor of IID Percolation on Trees, Exact Solution Algorithms for the Chordless Cycle Problem, Induced forests in some distance-regular graphs, Improved replica bounds for the independence ratio of random regular graphs, Perfect matchings as IID factors on non-amenable groups, Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs, Cubic graphs with small independence ratio, Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs

Cites Work

• Maximum induced trees in graphs
• The asymptotic distribution of short cycles in random regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• On the feedback vertex set problem in permutation graphs
• Fragmentability of graphs
• Differential equations for random processes and random graphs
• Large independent sets in regular graphs of large girth
• Decycling numbers of random regular graphs
• On the Independent Domination Number of Random Regular Graphs