Characteristic flows on signed graphs and short circuit covers

zbMATH Open1344.05066arXiv1407.5268MaRDI QIDQ311542FDOQ311542

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

Publication date: 13 September 2016

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

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

Full work available at URL: https://arxiv.org/abs/1407.5268

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

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

zbMATH Keywords

signed graphflows

Mathematics Subject Classification ID

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

Cites Work

• Signed graphs
• Title not available (Why is that?)
• Nowhere-zero integral flows on a bidirected graph
• Short cycle covers and the cycle double cover conjecture
• On flows in bidirected graphs
• A Class Of Abelian Groups
• Circuit covers of signed graphs
• Covering Multigraphs by Simple Circuits
• Flows in 3-edge-connected bidirected graphs
• Circular flow on signed graphs
• Shortest coverings of graphs with cycles

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)