Characteristic flows on signed graphs and short circuit covers

2014/07/20 by Macajova, Edita, Skoviera, Martin · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1407.5268

Abstract

We generalise to signed graphs a classical result of Tutte [Canad. J. Math. 8 (1956), 13--28] stating that every integer flow can be expressed as a sum of characteristic flows of circuits. In our generalisation, the rôle of circuits is taken over by signed circuits of a signed graph which occur in two types -- either balanced circuits or pairs of disjoint unbalanced circuits connected with a path intersecting them only at its ends. As an application of this result we show that a signed graph G admitting a nowhere-zero k-flow has a covering with signed circuits of total length at most 2(k-1)|E(G)|.

Cited by

• On the foundations of signed graphs I: chain groups, frame matroid, and bivariate flow polynomial

Related

• Shorter signed circuit covers of graphs
• Nowhere-zero flows in signed graphs: A survey
• Nowhere-zero flows on signed supereulerian graphs
• Classification of Indecomposable Flows of Signed Graphs
• Flow polynomials of a signed graph