Filling the gap between Turán's theorem and Pósa's conjecture

Details Filling the gap between Turán's theorem and Pósa's conjecture Filling the gap between Turán's theorem and Pósa's conjecture

2009-06-18

arxiv.org/abs/0906.3299v3

Mathematics

Combinatorics

44 pages, 2 figures; small errors corrected

Scientific paper

Much of extremal graph theory has concentrated either on finding very small subgraphs of a large graph (Turan-type results) or on finding spanning subgraphs (Dirac-type results). In this paper we are interested in finding intermediate-sized subgraphs. We investigate minimum degree conditions under which a graph G contains squared paths and squared cycles of arbitrary specified lengths. We determine precise thresholds, assuming that the order of G is large. This extends results of Fan and Kierstead [J. Combin. Theory Ser. B 63 (1995), 55--64] and of Komlos, Sarkozy, and Szemeredi [Random Structures Algorithms 9 (1996), 193--211] concerning the containment of a spanning squared path and a spanning squared cycle, respectively. Our results show that such minimum degree conditions constitute not merely an interpolation between the corresponding Turan-type and Dirac-type results, but exhibit other interesting phenomena.

Affiliated with

Also associated with

No associations

Rating

Filling the gap between Turán's theorem and Pósa's conjecture 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 Filling the gap between Turán's theorem and Pósa's conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Filling the gap between Turán's theorem and Pósa's conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-725318