Paths with many shortcuts in tournaments

Abstract

A shortcut of a directed path $v_1{v}_2\cdots v_n$ is an edge $v_i{v}_j$ with $j>i+1$. If $j=i+2$ the shortcut is called a hop. If all hops are present, the path is called hop complete, so the path and its hops form a square of a path. We prove that every tournament with $n\ge 4$ vertices has a Hamiltonian path with at least $(4n-10)/7$ hops, and has a hop complete path of order at least $n^{0.295}$. A spanning binary tree of a tournament is a spanning shortcut tree if for every vertex of the tree, all its left descendants are in-neighbors and all its right descendants are out-neighbors. It is well-known that every tournament contains a spanning shortcut tree. The number of shortcuts of a shortcut tree is the number of shortcuts of its unique induced Hamiltonian path. Let $t(n)$ denote the largest integer such that every tournament with $n$ vertices has a spanning shortcut tree with at least $t(n)$ shortcuts. We almost determine the asymptotic growth of $t(n)$ as it is proved that $\Theta (n{\log }^{2}n)\ge t(n)-\frac{1}{2}\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge \Theta (n\log n)$.

Cited by in corpus (2)

• Powers of paths and cycles in tournaments
• A Note on Powers of Paths in Tournaments