On the Maximum Order of Induced Paths and Induced Forests in Regular Graphs

2019/11/06 by Saieed Akbari, Akbari, Saieed, Alireza Amanihamedani +7
Computer Science · Mathematics · #05C38 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1911.02332

openalex publication_date 2019/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be a graph and a(G), LIF(G) denote the maximum orders of an induced forest and an induced linear forest of G, respectively. It is well-known that if G is an r-regular graph of order n, then a(G) ≥ (2)/(r+1)n. In this paper, we generalize this result by showing that LIF(G) ≥ (2)/(r+1)n. It was proved that for every graph G, a(G) ≥ ∑_i=1ⁿ(2)/(d_i+1), where d₁, …, d_n is the degree sequence of G. Here, we conjecture that for every graph G with δ(G) ≥ 2, LIF(G) ≥ ∑_i=1ⁿ(2)/(d_i+1).

Related

• A Caro-Wei bound for induced linear forests in graphs
• New results on large induced forests in graphs
• Induced forests in regular graphs with large girth
• A quasi-optimal upper bound for induced paths in sparse graphs
• A lower bound on the order of the largest induced linear forest in triangle-free planar graphs