Abstract
Let (Formula presented.) be a (Formula presented.)-connected graph with (Formula presented.). In this paper we first prove that: For two distinct vertices (Formula presented.) and (Formula presented.) in(Formula presented.), it contains a path connecting (Formula presented.) and (Formula presented.) which passes through its any (Formula presented.) specified vertices with length at least the average degree of the vertices other than (Formula presented.) and (Formula presented.). Further, with this result, we prove that: If (Formula presented.) vertices and (Formula presented.) edges, then it contains a cycle of length at least (Formula presented.) passing through its any (Formula presented.) specified vertices. Our results generalize a theorem of Fan on the existence of long paths and a classical theorem of Erdős and Gallai on the existence of long cycles under the average degree condition.
| Original language | English |
|---|---|
| Pages (from-to) | 279-295 |
| Number of pages | 17 |
| Journal | Graphs and Combinatorics |
| Volume | 32 |
| Issue number | 1 |
| DOIs | |
| State | Published - 1 Jan 2016 |
Keywords
- Average degree
- Long cycle
- Long path