Abstract | ||
---|---|---|
A graph G is ℓ-hamiltonian if each linear forest F with ℓ edges contained in G can be extended to a hamiltonian cycle of G. We give a sharp upper bound for the maximum number of cliques of a fixed size in a non-ℓ-hamiltonian graph. Furthermore, we prove stability: if a non-ℓ-hamiltonian graph contains almost the maximum number of cliques, then it is a subgraph of one of two extremal graphs. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1016/j.disc.2019.03.008 | Discrete Mathematics |
Keywords | Field | DocType |
Turán problem,Hamiltonian cycles,Extremal graph theory | Discrete mathematics,Graph,Combinatorics,Hamiltonian (quantum mechanics),Hamiltonian path,Upper and lower bounds,Extremal graph theory,Mathematics | Journal |
Volume | Issue | ISSN |
342 | 7 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zoltán Füredi | 1 | 1237 | 233.60 |
Alexandr V. Kostochka | 2 | 682 | 89.87 |
Ruth Luo | 3 | 8 | 2.75 |