Minimum $T$-Joins and Signed-Circuit Covering

Abstract

Let $G$ be a graph and $T$ be a vertex subset of $G$ with even cardinality. A $T$-join of $G$ is a subset $J$ of edges such that a vertex of $G$ is incident with an odd number of edges in $J$ if and only if the vertex belongs to $T$. Minimum $T$-joins have many applications in combinatorial optimizations. In this paper, we show that a minimum $T$-join of a connected graph $G$ has at most $|E(G)|-\frac{1}{2}|E(\hat{G})|$ edges where $\hat{G}$ is the maximum bidegeless subgraph of $G$. Further, we are able to use this result to show that every flow-admissible signed graph $(G,\sigma )$ has a signed-circuit cover with length at most $\frac{19}{6}|E(G)|$. Particularly, a 2-edge-connected signed graph $(G,\sigma )$ with even negativeness has a signed-circuit cover with length at most $\frac{8}{3}|E(G)|$.