1. Long Paths and Cycles Passing Through Specified Vertices Under the Average Degree Condition.
- Author
-
Li, Binlong, Ning, Bo, and Zhang, Shenggui
- Subjects
- *
PATHS & cycles in graph theory , *GRAPH theory , *GEOMETRIC vertices , *ARITHMETIC mean , *GRAPH connectivity , *MATHEMATICAL proofs - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF