Induced forests in some distance-regular graphs

DOI10.1016/J.DAM.2023.12.003arXiv2301.05207OpenAlexW4390238367MaRDI QIDQ6153467FDOQ6153467

Authors: Karen Gunderson, K. Meagher, Joy Morris, Venkata Raghu Tej Pantangi 

Publication date: 14 February 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: In this article, we study the order and structure of the largest induced forests in some families of graphs. First we prove a variation of the ratio bound that gives an upper bound on the order of the largest induced forest in a graph. Next we define a extsl{canonical induced forest} to be a forest that is formed by adding a vertex to a coclique and give several examples of graphs where the maximal forest is a canonical induced forest. These examples are all distance-regular graphs with the property that the Delsarte-Hoffman ratio bound for cocliques holds with equality. We conclude with some examples of related graphs where there are induced forests that are larger than a canonical forest.

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

Recommendations

• Induced Forests in Regular Graphs with Large Girth
• Large induced forests in graphs
• On maximum induced forests in graphs
• On the maximum orders of an induced forest, an induced tree, and a stable set
• Average distance and maximum induced forest

zbMATH Keywords

distance-regular graphsinduced forestsacyclic number1-degenerate subgraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Cites Work

• Interlacing eigenvalues and graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Large induced degenerate subgraphs
• Large induced forests in sparse graphs
• Induced matchings
• Problems and results in extremal combinatorics. I.
• Maximum induced trees in graphs
• Decycling hypercubes
• Feedback vertex set in hypercubes
• Induced Forests in Regular Graphs with Large Girth
• Lower Bounds For Induced Forests in Cubic Graphs
• Decycling numbers of random regular graphs
• Maximum induced forests of planar graphs
• A new bound on the feedback vertex sets in cubic graphs
• Short proofs of some extremal results
• The Erdős-Ko-Rado theorem for vector spaces
• Maximum induced forests in random graphs
• Title not available (Why is that?)
• Induced trees in triangle-free graphs
• Decycling cubes and grids
• Large induced trees in \(K_r\)-free graphs
• On the order of the largest induced tree in a random graph
• Large induced matchings in random graphs
• Size of the largest induced forest in subcubic graphs of girth at least four and five
• Refined estimates concerning sumsets contained in the roots of unity
• Rooted induced trees in triangle-free graphs

This page was built for publication: Induced forests in some distance-regular graphs

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