Paths with Prescribed Endpoints in Semicomplete and Locally Semicomplete Digraphs
Abstract
We study two open path problems with prescribed endpoints posed by Bang-Jensen and Gutin. The first asks for a longest (x,y)-path in a semicomplete digraph. The second asks whether a locally semicomplete digraph has a Hamiltonian (x,y)-path. For semicomplete digraphs, we solve the first problem when the endpoints lie in different strong components. We also prove that if a non-Hamiltonian longest (x,y)-path omits a set of vertices, then these vertices together with x and y have a Hamiltonian (y,x)-path. This gives an equivalent cycle problem. We then give an exact algorithm that runs in polynomial time when the number of omitted vertices is fixed. For locally semicomplete digraphs, we determine the possible endpoints in the connected nonstrong case. Known results then leave only strong, nonsemicomplete, non-$4$-strong digraphs unresolved. Every such digraph of order at least five has a strong vertex cut of size at most three. Two examples show that a spanning directed path together with a vertex-disjoint directed cycle is not sufficient, and that vertices of one strong component need not occur consecutively on a Hamiltonian path.
Related
- Revisiting the directed pathwidth of h-semicomplete digraphs
- Spiral Endgames for Computing Singular Endpoints of Homotopy Paths
- Arc-disjoint Hamiltonian paths in Cayley digraphs with a normal difference subgroup
- Asymptotic expansions for random walks conditioned to stay positive with arbitrary endpoints
- On optimal endpoints for integral kernel operators
BibTeX
@misc{bai2026paths,
title = {{Paths with Prescribed Endpoints in Semicomplete and Locally Semicomplete Digraphs}},
author = {Hanzhi Bai and Jin Yan and Jia Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.17439},
eprint = {2608.17439},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.17439},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Paths with Prescribed Endpoints in Semicomplete and Locally Semicomplete Digraphs
AU - Hanzhi Bai
AU - Jin Yan
AU - Jia Zhou
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2608.17439
UR - https://arxiv.org/abs/2608.17439
AB - We study two open path problems with prescribed endpoints posed by Bang-Jensen and Gutin. The first asks for a longest (x,y)-path in a semicomplete digraph. The second asks whether a locally semicomplete digraph has a Hamiltonian (x,y)-path. For semicomplete digraphs, we solve the first problem when the endpoints lie in different strong components. We also prove that if a non-Hamiltonian longest (x,y)-path omits a set of vertices, then these vertices together with x and y have a Hamiltonian (y,x)-path. This gives an equivalent cycle problem. We then give an exact algorithm that runs in polynomial time when the number of omitted vertices is fixed. For locally semicomplete digraphs, we determine the possible endpoints in the connected nonstrong case. Known results then leave only strong, nonsemicomplete, non-$4$-strong digraphs unresolved. Every such digraph of order at least five has a strong vertex cut of size at most three. Two examples show that a spanning directed path together with a vertex-disjoint directed cycle is not sufficient, and that vertices of one strong component need not occur consecutively on a Hamiltonian path.
ER -