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≥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=(⋃i=1kP2ai)⋃(⋃i=1lP2bi+1) be k+l disjoint paths of order 2a1,…,2ak,2b1+1,…,2bl+1, respectively, where k≥0, 0≤l≤2, and k+l≥2. If the minimum degree δ(G)≥∑i=1kai+∑i=1lbi−1, then F⊆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. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.disc.2018.11.021 | Discrete Mathematics |
Keywords | Field | DocType |
Erdős–Gallai Theorem,Stable problem,Linear forest,Path | Graph,Discrete mathematics,Combinatorics,Disjoint sets,Connectivity,Stability theorem,Mathematics | Journal |
Volume | Issue | ISSN |
342 | 3 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ming-Zhu Chen | 1 | 0 | 0.34 |
Xiao-Dong Zhang | 2 | 97 | 19.87 |