Characteristic flows on signed graphs and short circuit covers

MaRDI QIDQ311542zbMATH OpenFDO

Authors E. Máčajová, Martin Škoviera

Publication date 13 September 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.5268, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p30

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

signed graphflows

Mathematics Subject Classification ID

Flows in graphs (05C21) Signed and weighted graphs (05C22)

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^ole 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)|$.

Recommendations

• Shorter signed circuit covers of graphs
• Circuit covers of signed graphs
• Flows on flow-admissible signed graphs
• Circuit \(k\)-covers of signed graphs
• Circuit covers of cubic signed graphs

Cites work

• scientific article; zbMATH DE number 4075098 (Why is no real title available?)
• A Class Of Abelian Groups
• Circuit covers of signed graphs
• Circular flow on signed graphs
• Covering Multigraphs by Simple Circuits
• Flows in 3-edge-connected bidirected graphs
• Nowhere-zero integral flows on a bidirected graph
• On flows in bidirected graphs
• Short cycle covers and the cycle double cover conjecture
• Shortest coverings of graphs with cycles
• Signed graphs

Cited in

(12)

• Shorter signed circuit covers of graphs
• On 2k-twisted graphs
• Nowhere-zero flows on signed Eulerian graphs
• Signed graphs: from modulo flows to integer-valued flows
• Circuit \(k\)-covers of signed graphs
• Flow polynomials of a signed graph
• The flow and tension spaces and lattices of signed graphs
• Conformal decomposition of integral flows on signed graphs with outer-edges
• Resolution of indecomposable integral flows on signed graphs
• Multiple weak 2-linkage and its applications on integer flows of signed graphs
• Flows on signed graphs without long barbells
• Generalizing Kirchhoff laws for signed graphs

This page was built for publication: Characteristic flows on signed graphs and short circuit covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q311542)