Path odd-covers of graphs
Discrete Mathematics · 2026-09 · 349 (9) · 115078
DOI: 10.1016/j.disc.2026.115078 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics, 2026-09. Verfasst von Steffen Borgwardt und 5 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: National Science Foundation, Air Force Office of Scientific Research.
Abstract (Originalsprache)
We introduce and study"path odd-covers", a weakening of Gallai's path decomposition problem and a strengthening of the linear arboricity problem. The"path odd-cover number"$p_2(G)$ of a graph $G$ is the minimum cardinality of a collection of paths whose vertex sets are contained in $V(G)$ and whose symmetric difference of edge sets is $E(G)$. We prove an upper bound on $p_2(G)$ in terms of the maximum degree $\Delta$ and the number of odd-degree vertices $v_{\text{odd}}$ of the form $\max\left\{{v_{\text{odd}}}/{2}, 2\left\lceil {\Delta}/{2}\right \rceil\right\}$. This bound is only a factor of $2$ from a rather immediate lower bound of the form $\max \left\{ {v_{\text{odd}} }/{2} , \left\lceil {\Delta}/{2}\right\rceil \right\}$. We also investigate some natural relaxations of the problem which highlight the connection between the path odd-cover number and other well-known graph parameters. For example, when allowing for subdivisions of $G$, the previously mentioned lower bound is always tight except in some trivial cases. Further, a relaxation that allows for the addition of isolated vertices to $G$ leads to a match with the linear arboricity when $G$ is Eulerian. Finally, we transfer our observations to establish analogous results for cycle odd-covers.
Förderung
- National Science Foundation
- Air Force Office of Scientific Research
Zitieren
APA
Borgwardt, S., Buchanan, C., Culver, E., Frederickson, B., Rombach, P., & Yoo, Y. (2026). Path odd-covers of graphs. Discrete Mathematics, 349(9), 115078. https://doi.org/10.1016/j.disc.2026.115078
Vancouver
Borgwardt S, Buchanan C, Culver E, Frederickson B, Rombach P, Yoo Y. Path odd-covers of graphs. Discrete Mathematics. 2026;349(9):115078. doi:10.1016/j.disc.2026.115078
BibTeX
@article{Borgwardt2026,
author = {Borgwardt, Steffen and Buchanan, Calum and Culver, Eric and Frederickson, Bryce and Rombach, Puck and Yoo, Youngho},
title = {Path odd-covers of graphs},
journal = {Discrete Mathematics},
year = {2026},
volume = {349},
number = {9},
pages = {115078},
doi = {10.1016/j.disc.2026.115078}
}
EUVIMED