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 (9)

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

This page was built for publication: Induced Forests in Regular Graphs with Large Girth