Circuit covers of cubic signed graphs. Issue 1 (1st February 2018) - Wu, Yezhou; Ye, Dong
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.