2026-04-01
Path decompositions of oriented graphs
Publication
Publication
European Journal of Combinatorics , Volume 134 p. 104346:1- 104346:16
We consider the problem of decomposing the edges of a digraph into as few paths as possible. A natural lower bound for the number of paths in any path decomposition of a digraph D is 12∑v∈V(D)|d+(v)−d−(v)|; any digraph that achieves this bound is called consistent. Alspach et al. 1976 conjectured in 1976 that every tournament of even order is consistent and this was recently verified for large tournaments by Girão et al. 2023. A more general conjecture of Pullman (Reid and Wayland, 1987) states that for odd d, every orientation of a d-regular graph is consistent. We prove that the conjecture holds for random d-regular graphs with high probability i.e. for fixed odd d and as n→∞ the conjecture holds for almost all d-regular graphs. Along the way, we verify Pullman’s conjecture for graphs whose girth is sufficiently large (as a function of the degree).
| Additional Metadata | |
|---|---|
| doi.org/10.1016/j.ejc.2026.104346 | |
| European Journal of Combinatorics | |
| Networks COFUND postdocs , Networks , Alain Bensoussan Career Development Enchancer | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Patel, V., & Yıldız, M. A. (2026). Path decompositions of oriented graphs. European Journal of Combinatorics, 134, 104346:1–104346:16. doi:10.1016/j.ejc.2026.104346 |
|
