Induced forests in some distance-regular graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910411390976000 |
|---|---|
| author | Gunderson, Karen Meagher, Karen Morris, Joy Pantangi, Venkata Raghu Tej |
| author_facet | Gunderson, Karen Meagher, Karen Morris, Joy Pantangi, Venkata Raghu Tej |
| contents | 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 \textsl{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_05207 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Induced forests in some distance-regular graphs Gunderson, Karen Meagher, Karen Morris, Joy Pantangi, Venkata Raghu Tej Combinatorics 05C69, 05C35, 05C25 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 \textsl{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. |
| title | Induced forests in some distance-regular graphs |
| topic | Combinatorics 05C69, 05C35, 05C25 |
| url | https://arxiv.org/abs/2301.05207 |