| Autor: |
Gunderson, Karen, Meagher, Karen, Morris, Joy, Pantangi, Venkata Raghu Tej |
| Rok vydání: |
2023 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| DOI: |
10.1016/j.dam.2023.12.003 |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
