We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Long Paths and Cycles Passing Through Specified Vertices Under the Average Degree Condition.
- Authors
Li, Binlong; Ning, Bo; Zhang, Shenggui
- Abstract
Let $$G$$ be a $$k$$ -connected graph with $$k\ge 2$$ . In this paper we first prove that: For two distinct vertices $$x$$ and $$z$$ in $$G$$ , it contains a path connecting $$x$$ and $$z$$ which passes through its any $$k-2$$ specified vertices with length at least the average degree of the vertices other than $$x$$ and $$z$$ . Further, with this result, we prove that: If $$G$$ has $$n$$ vertices and $$m$$ edges, then it contains a cycle of length at least $$2m/(n-1)$$ passing through its any $$k-1$$ 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.
- Subjects
PATHS &; cycles in graph theory; GRAPH theory; GEOMETRIC vertices; ARITHMETIC mean; GRAPH connectivity; MATHEMATICAL proofs
- Publication
Graphs & Combinatorics, 2016, Vol 32, Issue 1, p279
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-015-1573-y