Skip to Main content Skip to Navigation
Journal articles

Powers of paths in tournaments

Abstract : In this short note we prove that every tournament contains the k -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when k =2, showing that there is always a square of a directed path of length, which is best possible.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-03269230
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Wednesday, November 10, 2021 - 12:53:41 PM
Last modification on : Sunday, June 26, 2022 - 3:18:58 AM
Long-term archiving on: : Friday, February 11, 2022 - 6:48:16 PM

File

powers-of-path-tournaments.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Nemanja Draganić, François Dross, Jacob Fox, António Girão, Frédéric Havet, et al.. Powers of paths in tournaments. Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2021, pp.1-5. ⟨10.1017/S0963548321000067⟩. ⟨hal-03269230⟩

Share

Metrics

Record views

46

Files downloads

85