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

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)\ge \frac{2}{r+1}n$. In this paper, we generalize this result by showing that LIF$(G)\ge \frac{2}{r+1}n$. It was proved that for every graph $G$, $a(G)\ge {\sum }_{i=1}^n\frac{2}{d_i+1}$, where $d_1,\dots ,d_n$ is the degree sequence of $G$. Here, we conjecture that for every graph $G$ with $\delta (G)\ge 2$, LIF$(G)\ge {\sum }_{i=1}^n\frac{2}{d_i+1}$.

9 pages, 1 algorithm, 2 tables