The Library
Minimum degree conditions for large subgraphs
Tools
Tools
Tools
Allen, Peter, Böttcher, Julia, Hladký, Jan and Cooley, Oliver (2009) Minimum degree conditions for large subgraphs. Electronic Notes in Discrete Mathematics, Vol.34 . pp. 75-79. doi:10.1016/j.endm.2009.07.013 ISSN 1571-0653.
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.1016/j.endm.2009.07.013
Abstract
Much of extremal graph theory has concentrated either on finding very small subgraphs of a large graph (such as Turán's theorem [Turán, P., On an extremal problem in graph theory (in Hungarian), Matematiko Fizicki Lapok 48 (1941), 436–452]) or on finding spanning subgraphs (such as Dirac's theorem [Dirac, G.A., Some theorems on abstract graphs, Proc. London Math. Soc. s3-2 (1952), 69–81] or more recently work of Komlós, Sárközy and Szemerédi [Komlós, J., G. N. Sárközy and E. Szemerédi, On the square of a Hamiltonian cycle in dense graphs, Random Struct. Algorithms 9 (1996), 193-211; Komlós, J., G. N. Sárközy and E. Szemerédi, Proof of the Seymour Conjecture for large graphs, Ann. Comb. 2 (1998), 43–60] towards a proof of the Pósa-Seymour conjecture). Only a few results give conditions to obtain some intermediate-sized subgraph. We contend that this neglect is unjustified. To support our contention we focus on the illustrative case of minimum degree conditions which guarantee squared-cycles of various lengths, but also offer results, conjectures and comments on other powers of paths and cycles, generalisations thereof, and hypergraph variants.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
| Journal or Publication Title: | Electronic Notes in Discrete Mathematics | ||||
| Publisher: | Elsevier BV | ||||
| ISSN: | 1571-0653 | ||||
| Official Date: | 2009 | ||||
| Dates: |
|
||||
| Volume: | Vol.34 | ||||
| Page Range: | pp. 75-79 | ||||
| DOI: | 10.1016/j.endm.2009.07.013 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
