Induced Forests in Regular Graphs with Large Girth

DOI10.1017/S0963548307008905zbMATH Open1185.05040arXiv0709.3126MaRDI QIDQ3545905FDOQ3545905

Authors: Carlos Hoppen, Nicholas Wormald 

Publication date: 11 December 2008

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

Abstract: An induced forest of a graph G is an acyclic induced subgraph of G. The present paper is devoted to the analysis of a simple randomised algorithm that grows an induced forest in a regular graph. The expected size of the forest it outputs provides a lower bound on the maximum number of vertices in an induced forest of G. When the girth is large and the degree is at least 4, our bound coincides with the best bound known to hold asymptotically almost surely for random regular graphs. This results in an alternative proof for the random case.

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

Recommendations

• The analysis of a prioritised probabilistic algorithm to find large induced forests in regular graphs with large girth
• Maximum induced forests in random graphs
• Forests in random graphs
• Large induced forests in graphs
• Large induced forests in planar graphs with girth 4

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (20)

• Maximum induced forests in graphs of bounded treewidth
• Large induced forests in planar graphs with girth 4
• Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
• Exact Solution Algorithms for the Chordless Cycle Problem
• Induced forests in some distance-regular graphs
• The analysis of a prioritised probabilistic algorithm to find large induced forests in regular graphs with large girth
• Percolation with small clusters on random graphs
• Factor of iid percolation on trees
• On maximum induced forests in graphs
• Induced graphs of uniform spanning forests
• Maximum induced forests in random graphs
• Forests and trees among Gallai graphs
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• Cubic graphs with small independence ratio
• Perfect matchings as IID factors on non-amenable groups
• Improved replica bounds for the independence ratio of random regular graphs
• Induced forests in bipartite planar graphs
• The forest number in several classes of regular graphs
• Forests in random graphs
• Well-indumatched Trees and Graphs of Bounded Girth

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3545905)