Circuit covers of cubic signed graphs. Issue 1 (1st February 2018)

• Record Type: Journal Article
• Authors: Wu, Yezhou; Ye, Dong
• Is Part Of: Journal of graph theory. Volume 89:Issue 1(2018)
• Page Start: 40
• Page End: 54
• Publication Date: 2018-02-01
• Subjects: signed‐circuit cover -- signed graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22238
• Languages: English
• ISSNs: 0364-9024

Abstract

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.