Papers
arxiv:2306.06487

Path Odd-Covers of Graphs

Published on Jun 10, 2023
Authors:
,
,
,
,
,

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 Δ and the number of odd-degree vertices v_{odd} of the form maxleft{v_{odd}/{2}, 2leftlceil Δ/{2}right rceilright}. This bound is only a factor of 2 from a rather immediate lower bound of the form max left{ {v_{odd} }/{2} , leftlceil Δ/{2}rightrceil 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.

Community

Sign up or log in to comment

Get this paper in your agent:

hf papers read 2306.06487
Don't have the latest CLI?
curl -LsSf https://hf.co/cli/install.sh | bash

Models citing this paper 0

No model linking this paper

Cite arxiv.org/abs/2306.06487 in a model README.md to link it from this page.

Datasets citing this paper 0

No dataset linking this paper

Cite arxiv.org/abs/2306.06487 in a dataset README.md to link it from this page.

Spaces citing this paper 0

No Space linking this paper

Cite arxiv.org/abs/2306.06487 in a Space README.md to link it from this page.

Collections including this paper 0

No Collection including this paper

Add this paper to a collection to link it from this page.