Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.endm.2009.07.013 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
extremal graph theory,minimum degree,large subgraphs | Graph theory,Discrete mathematics,Graph,Combinatorics,Line graph,Hamiltonian path,Hypergraph,Dirac (video compression format),Extremal graph theory,Conjecture,Mathematics | Journal |
Volume | ISSN | Citations |
34 | 1571-0653 | 1 |
PageRank | References | Authors |
0.41 | 2 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Allen | 1 | 56 | 9.72 |
| Julia Böttcher | 2 | 93 | 17.35 |
| Jan Hladký | 3 | 113 | 18.59 |
| Oliver Cooley | 4 | 39 | 9.15 |