Circuit Covers of Cubic Signed Graphs

Abstract

A signed graph is a graph $G$ associated with a mapping $\sigma :E(G)\to \{-1,+1\}$, denoted by $(G,\sigma )$. A $cycle$ of $(G,\sigma )$ is a connected 2-regular subgraph. A cycle $C$ is $positive$ if it has an even number of negative edges, and negative otherwise. A $circuit$ of of a signed graph $(G,\sigma )$ is a positive cycle or a barbell consisting of two edge-disjoint negative cycles joined by a path. The definition of a circuit of signed graph comes from the signed-graphic matroid. A circuit cover of $(G,\sigma )$ is a family of circuits covering all edges of $(G,\sigma )$. A circuit cover with the smallest total length is called a shortest circuit cover of $(G,\sigma )$ and its length is denoted by $\text{scc}(G,\sigma )$. Bouchet proved that a signed graph with a circuit cover if and only if it is flow-admissible (i.e., has a nowhere-zero integer flow). Máčajová et. al. show that a 2-edge-connected signed graph $(G,\sigma )$ has $\text{scc}(G,\sigma )\le 9|E(G)|$ if it is flow-admissible. This bound was improved recently by Cheng et. al. to $\text{scc}(G,\sigma )\le 11|E(G)|/3$ for 2-edge-connected signed graphs with even negativeness, and particularly, $\text{scc}(G,\sigma )\le 3|E(G)|+\epsilon (G,\sigma )/3$ for 2-edge-connected cubic signed graphs with even negativeness (where $\epsilon (G,\sigma )$ is the negativeness of $(G,\sigma )$). In this paper, we show that every 2-edge-connected cubic signed graph has $\text{scc}(G,\sigma )\le 26|E(G)|/9$ if it is flow-admissible, and $\text{scc}(G,\sigma )\le 23|E(G)|/9$ if it has even negativeness.

13 pages, 2 figures