EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Path odd-covers of graphs

Steffen Borgwardt, Calum Buchanan, Eric Culver, Bryce Frederickson, Puck Rombach, Youngho Yoo

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →