Erdos-Gallai Stability Theorem for Linear Forests

Abstract

The Erdős-Gallai Theorem states that every graph of average degree more than $l-2$ contains a path of order $l$ for $l\ge 2$. In this paper, we obtain a stability version of the Erdős-Gallai Theorem in terms of minimum degree. Let $G$ be a connected graph of order $n$ and $F=({\bigcup }_{i=1}^k{P}_{2a_i})\bigcup ({\bigcup }_{i=1}^l{P}_{2b_i+1})$ be $k+l$ disjoint paths of order $2a_1,\dots ,2a_k,2b_1+1,\dots ,2b_l+1,$ respectively, where $k\ge 0$, $0\le l\le 2$, and $k+l\ge 2$. If the minimum degree $\delta (G)\ge {\sum }_{i=1}^k{a}_i+{\sum }_{i=1}^l{b}_i-1$, then $F\subseteq G$ except several classes of graphs for sufficiently large $n$, which extends and strengths the results of Ali and Staton for an even path and Yuan and Nikiforov for an odd path.

21 pages, 4 figures

References in corpus (1)

• Turàn numbers of Multiple Paths and Equibipartite Trees