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. doi:10.1112/jlms/jdr007 ISSN 0024-6107.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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, Engineering and Medicine > 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 | ||||
| Official Date: | October 2011 | ||||
| Dates: |
|
||||
| Volume: | Vol.84 | ||||
| Number: | No.2 | ||||
| Number of Pages: | 74 | ||||
| Page Range: | pp. 269-302 | ||||
| DOI: | 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), |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
