Path Odd-Covers of Graphs

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

Publication date 10 June 2023

Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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

D e l t a

and the number of odd-degree vertices

v_{e x t o d d}

of the form

m a x l e f t v_{e x t o d d} / 2, 2 l e f t l c e i l D e l t a / 2 i g h t c e i l i g h t

. This bound is only a factor of

2

from a rather immediate lower bound of the form

m a x l e f t v_{e x t o d d} / 2, l e f t l c e i l D e l t a / 2 i g h t c e i l i g h t

. 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.

This page was built for publication: Path Odd-Covers of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439897)