The Library
Filling the gap between Turan's theorem and Posa's conjecture
Tools
Tools
Tools
Allen, Peter D., Böttcher, Julia and Hladký, Jan. (2011) Filling the gap between Turan's theorem and Posa's conjecture. Journal of the London Mathematical Society, Vol.84 (No.2). pp. 269-302. ISSN 0024-6107
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1112/jlms/jdr007
Abstract
Much of extremal graph theory has concentrated either on finding very small subgraphs of a large graph (Turán-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 Komlós, Sarközy and Szemerédi [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 Turán-type and Dirac-type results, but exhibit other interesting phenomena.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Faculty of Science > Mathematics |
| Library of Congress Subject Headings (LCSH): | Graph theory |
| Journal or Publication Title: | Journal of the London Mathematical Society |
| Publisher: | Cambridge University Press |
| ISSN: | 0024-6107 |
| Date: | October 2011 |
| Volume: | Vol.84 |
| Number: | No.2 |
| Number of Pages: | 74 |
| Page Range: | pp. 269-302 |
| Identification Number: | 10.1112/jlms/jdr007 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), Technische Universität München (TUM), Deutsche Forschungsgemeinschaft (DFG), Univerzita Karlova (UK), Deutscher Akademischer Austauschdienst (DAAD), Bayerisches Hochschulzentrum für Mittel-, Ost- und Südosteuropa (BAYHOST) |
| Grant number: | EP/D063191/1 (EPSRC), TA 309/2-1 (DFG), GAUK 202-10/258009 (UK), |
| URI: | http://wrap.warwick.ac.uk/id/eprint/38737 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
