Circuit covers of cubic signed graphs.

Abstract: A signed graph, denoted by ( G , σ ), is a graph G associated with a mapping σ : E ( G ) → { − 1 , + 1 }. A cycle of ( G , σ ) is a connected 2‐regular subgraph. A cycle C is positive if it has an even number of negative edges, and negative otherwise. A signed‐circuit of a signed graph ( G , σ ) is a positive cycle or a barbell consisting of two edge‐disjoint negative cycles joined by a path. The definition of a signed‐circuit of signed graph comes from the signed‐graphic matroid. A signed‐circuit cover of ( G , σ ) is a family of signed‐circuits covering all edges of ( G , σ ). A signed‐circuit cover with the smallest total length is called a shortest signed‐circuit cover of ( G , σ ) and its length is denoted by scc ( G , σ ). Bouchet proved that a signed graph has a signed‐circuit cover if and only if it is flow‐admissible (i.e., has a nowhere‐zero integer flow). In this article, we show that a 3‐connected flow‐admissible signed graph does not necessarily have a signed‐circuit double cover. For shortest signed‐circuit cover of 2‐edge‐connected cubic signed graphs ( G , σ ), we show that scc ( G , σ ) < 26 | E ( G ) | / 9 if it is flow‐admissible. [ABSTRACT FROM AUTHOR]