Circuit Covers of Signed Graphs
Edita Máčajová, André Raspaud, Edita Rollová, Martin Škoviera · Journal of Graph Theory · 2015
We introduce the concept of a signed circuit cover of a signed graph. A signed circuit cover is a natural analog of a circuit cover of a graph and is equivalent to a covering of the corresponding signed graphic matroid with circuits. As in the case of graphs, a signed graph has a signed circuit cover only when it admits a nowhere-zero integer flow. In the present article, we establish the existence of a universal coefficient such that every signed graph G that admits a nowhere-zero integer flow has a signed circuit cover of total length at most . We show that if G is bridgeless, then , and in the general case .