Path Extendable Tournaments

Zan-Bo Zhang Weihua He Hajo Broersma Xiaoyan Zhang · 2025

Read Path Extendable Tournaments by Zan-Bo Zhang Weihua He Hajo Broersma Xiaoyan Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-21653.txt.

Introduction

Zan-Bo Zhang, Weihua He, Hajo Broersma, and Xiaoyan Zhang prove results about directed graphs in a 2025 math paper. A tournament is a directed graph where each pair of points is joined by one arrow. A tournament is path extendable if any path that misses some points can be rebuilt, with the same ends, to include one more point.

Earlier work tied steady path lengths in tournaments to two measures, one for imbalance and one for short two step paths. The authors give two new conditions, in terms of those measures, that ensure a tournament is path extendable. One compares the two measures directly, and the other sets a floor for the short path measure alone. As a result, they show that almost all random tournaments have this trait.

Catalog record

CREATORZan-Bo Zhang Weihua He Hajo Broersma Xiaoyan Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-21653

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Path Extendable Tournaments Zan-Bo Zhang Weihua He Hajo Broersma Xiaoyan Zhang Abstract A digraph D D is called path extendable if for every nonhamiltonian (directed) path P P in D D , there exists another path P ′ P^{\prime} with the same initial and terminal vertices as P P , and V ⁡ ( P ′ ) = V ⁡ ( P ) ∪ { w } V(P^{\prime})=V(P)\cup\{w\} for a vertex w ∈ V ⁡ ( D ) ∖ V ⁡ ( P ) w\in V(D)\setminus V(P) . Hence, path extendability implies paths of continuous lengths between every vertex pair. In earlier works of C. Thomassen and K. Zhang, it was shown that the condition of small i ⁡ ( T ) i(T) or positive π 2 ​ ( T ) \pi_{2}(T) implies paths of continuous lengths between every vertex pair in a tournament T T , where i ⁡ ( T ) i(T) is the irregularity of T T and π 2 ​ ( T ) \pi_{2}(T) denotes for the minimum number of paths of length 2 2 from u u to v v among all vertex pairs { u , v } \{u,v\} . Motivated by these results, we study sufficient conditions in terms of i ⁡ ( T ) i(T) and π 2 ​ ( T ) \pi_{2}(T) that guarantee a tournament T T is path extendable. We prove that (1) a tournament T T is path extendable if i ⁡ ( T ) < 2 ​ π 2 ​ ( T ) − ( | T | + 8 ) / 6 i(T)<2\pi_{2}(T)-(|T|+8)/6 , and (2) a tournament T T is path extendable if π 2 ​ ( T ) > ( 7 ​ | T | − 10 ) / 36 \pi_{2}(T)>(7|T|-10)/36 . As an application, we deduce that almost all random tournaments are path extendable. Key words : path, path extendability, tournament, random tournament 1 Introduction, terminology and notation It is commonly known that tournaments have a rich path and cycle structure. As an example, every tournament has a hamiltonian path, and every strong tournament is hamiltonian, vertex-pancyclic, and even cycle extendable (for cycle extendability a well-characterized class of exceptional graphs has to be excluded, see [ 5 , 9 ] ). However, many stronger properties involving connecting paths of specific lengths, such as hamiltonian-connectedness, panconnectedness and path extendability, do not generally hold in tournaments. Since the late 1960s, many researchers have devoted themselves to finding sufficient conditions for these properties. Throughout the paper, we use n or |D| to denote the number of vertices of a digraph D . Let D be a digraph on n\geq 2 vertices, and let u,v\in V(D) be two distinct vertices. We use the term k -path to indicate a directed path of length k , i.e., containing k arcs, and (u,v) - k -path as shorthand for a k -path from u to v . Adopting the terminology of Thomassen [ 12 ] , a digraph D is said to be weakly hamiltonian-connected if for any distinct x,y\in V(D) there exists a hamiltonian path from x to y or from y to x , and D is called strongly hamiltonian-connected if for any distinct x,y\in V(D) there exists a hamiltonian path from x to y and from y to x . Similarly, in [ 12 ] , D is called weakly panconnected if for any distinct x,y\in V(D) there exists an (x,y) - k -path or a (y,x) - k -path for every integer k with 3\leq k\leq n-1 , and strongly panconnected if for any distinct x,y\in V(D) there exists an (x,y) - k -path and a (y,x) - k -path for every integer k with 3\leq k\leq n-1 . In [ 12 ] , Thomassen characterized all weakly hamiltonian-connected tournaments, and showed that for a tournament being weakly hamiltonian-connected is equivalent to being weakly panconnected. He also proved that being 4 -strong is a sufficient condition for a tournament to be strongly hamiltonian-connected. Here a digraph D is called k -strong if D-A is strongly connected for any set A\subseteq V(D) with at most k-1 vertices. Then, strengthening a result of Alspach et al., he showed that a tournament T that is close to regular, or to be precise, with small irregularity i(T)\triangleq\max\{|d^{+}(u)-d^{-}(u)|\mid u\in V(T)\} , is strongly panconnected. Note that in a tournament the condition of irregularity can be turned into a degree condition as \min\{\delta^{+}(T),\delta^{-}(T)\}=\frac{n-i(T)-1}{2}. (1) Theorem 1.1 . (Thomassen [ 12 ] ) If T is a tournament on n\geq 5k+21 vertices with i(T)\leq k , then T is strongly panconnected. Note that in the definition of strongly panconnectedness the existence of paths of length 2 is not required. A more restrictive concept which includes the existence of 2 -paths was studied by Zhang in [ 13 ] . There he defines a digraph D to be completely strong path-connected if there exists a (u,v) - k -path and a (v,u) - k -path in D for every distinct u\in V(D) and v\in V(D) and every integer k with 2\leq k\leq n-1 . Let T be a tournament. We denote the number of distinct (u,v) - 2 -paths in T by p_{2}(u,v) , and we let \pi_{2}(T)=\min\{p_{2}(u,v)\mid u,v\in V(T)\} be the global infimum of p_{2}(u,v) , where u and v are distinct vertices of T . In [ 13 ] , Zhang presented the following characterization of completely strong path-connected tournaments in terms of \pi_{2}(T) . Theorem 1.2 . (Zhang [ 13 ] ) A tournament T on n vertices is completely strong path-connected if and only if \pi_{2}(T)\geq 1 , unless T belongs to one well-characterized class of exceptional graphs. Motivated by the aforementioned structural results on tournaments and the results due to Hendry on path extendability in undirected graphs [ 7 ] , we focus on the analogous concept of path extendability in tournaments. For this purpose, we say that a nonhamiltonian path P in a digraph D is extendable , if there exists another path P^{\prime} in D with the same initial vertex and terminal vertex as P , and with V(P^{\prime})=V(P)\cup\{w\} for some vertex w\in V(D)\setminus V(P) (note that Faudree and Gyárfás [ 4 ] study another kind of path extendability in tournaments, which extends a path from one of its endpoints). Moreover, by including the following specific length restriction, a digraph D is called \{k+\} -path extendable , if every nonhamiltonian path of length at least k is extendable in D . And naturally, we use the shorter term path extendability for \{1+\} -path extendability. The current authors have studied path extendability in tournaments, and obtained the following result, in which the structure of the exceptional graphs will be described in Section 4 and be used to prove Theorem 2.3 . Theorem 1.3 . (Zhang et al. [ 15 ] ) A regular tournament T with at least 7 vertices is \{2+\} -path extendable, unless T\in\mathcal{T}_{1} , T\in\mathcal{T}_{2} or T=T_{0} . Reflecting on Bondy’s idea in his meta-conjecture on hamiltonian undirected graphs [ 3 ] , and considering results of Bondy on pancyclicity [ 2 ] and Hendry on cycle extendability [ 6 ] and path extendability

Read the complete text