Long paths and cycles passing through specified vertices under the average degree condition

Details Long paths and cycles passing through specified vertices under the average degree condition Long paths and cycles passing through specified vertices under the average degree condition

2011-09-20

arxiv.org/abs/1109.4344v2

Mathematics

Combinatorics

Scientific paper

Let $G$ be a $k$-connected graph with $k\geq 2$. In this paper we first prove that: For two distinct vertices $x$ and $z$ in $G$, it contains a path passing 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\"os and Gallai on the existence of long cycles under the average degree condition.

Affiliated with

Also associated with

No associations

Rating

Long paths and cycles passing through specified vertices under the average degree condition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Long paths and cycles passing through specified vertices under the average degree condition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Long paths and cycles passing through specified vertices under the average degree condition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147640