A variation of a theorem by Pósa
| Autor: | Zoltán Füredi, Alexandr V. Kostochka, Ruth Luo |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Hamiltonian path Upper and lower bounds Graph Theoretical Computer Science Extremal graph theory Combinatorics symbols.namesake 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering symbols Discrete Mathematics and Combinatorics Mathematics::Symplectic Geometry Mathematics |
| Zdroj: | Discrete Mathematics. 342:1919-1923 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2019.03.008 |
| Popis: | A graph G is l -hamiltonian if each linear forest F with l 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- l -hamiltonian graph. Furthermore, we prove stability: if a non- l -hamiltonian graph contains almost the maximum number of cliques, then it is a subgraph of one of two extremal graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect