Induced forests in some distance-regular graphs

DOI10.1016/J.DAM.2023.12.003MaRDI QIDQ6153467zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Describes a project that uses

Uses Software

• SageMath

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)