DIKUL - logo
E-resources
Full text
Peer reviewed Open access
  • Induced forests in some dis...
    Gunderson, Karen; Meagher, Karen; Morris, Joy; Pantangi, Venkata Raghu Tej

    Discrete Applied Mathematics, 03/2024, Volume: 346
    Journal Article

    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 Delsarte–Hoffman ratio bound for cocliques that gives an upper bound on the order of the largest induced forest in a graph. Next we define a 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.