Minimum Degrees for Powers of Paths and Cycles

0570691 - ÚI 2024 RIV US eng J - Journal Article
Hng, Eng Keat
Minimum Degrees for Powers of Paths and Cycles.
SIAM Journal on Discrete Mathematics. Roč. 36, č. 4 (2022), s. 2667-2736. ISSN 0895-4801. E-ISSN 1095-7146
Institutional support: RVO:67985807
Keywords : paths * cycles * graph power * minimum degree
OECD category: Pure mathematics
Impact factor: 0.8, year: 2022
Method of publishing: Limited access
https://doi.org/10.1137/20M1359183

We study minimum degree conditions under which a graph G contains kth powers of paths and cycles of arbitrary specified lengths. We determine precise thresholds, assuming that the order of G is large. This extends a result of Allen, Böttcher, and Hladký [J. Lond. Math. Soc. (2), 84 (2011), pp. 269--302] concerning the containment of squares of paths and squares of cycles of arbitrary specified lengths and settles a conjecture of theirs in the affirmative.
Permanent Link: https://hdl.handle.net/11104/0342025