2018/03/09 by Wu, Yezhou, Ye, Dong
#05C38 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1803.03696
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(\widehat G )| edges where \widehat 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,σ) has a signed-circuit cover with length at most \frac19 6 |E(G)|. Particularly, a 2-edge-connected signed graph (G,σ) with even negativeness has a signed-circuit cover with length at most \frac 8 3 |E(G)|.