pith. sign in

arxiv: 1607.00053 · v1 · pith:CNJVLOANnew · submitted 2016-06-30 · 🧮 math.CO

Odd decompositions of eulerian graphs

classification 🧮 math.CO
keywords conjectureeuleriangraphadmitscloseddecompositiongraphssigned
0
0 comments X
read the original abstract

We prove that an eulerian graph $G$ admits a decomposition into $k$ closed trails of odd length if and only if and it contains at least $k$ pairwise edge-disjoint odd circuits and $k\equiv |E(G)|\pmod{2}$. We conjecture that a connected $2d$-regular graph of odd order with $d\ge 1$ admits a decomposition into $d$ odd closed trails sharing a common vertex and verify the conjecture for $d\le 3$. The case $d=3$ is crucial for determining the flow number of a signed eulerian graph which is treated in a separate paper (arXiv:1408.1703v2). The proof of our conjecture for $d=3$ is surprisingly difficult and calls for the use of signed graphs as a convenient technical tool.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.