Premium
Circuit Covers of Signed Graphs
Author(s) -
Máčajová Edita,
Raspaud André,
Rollová Edita,
Škoviera Martin
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21866
Subject(s) - signed graph , mathematics , combinatorics , discrete mathematics , matroid , cover (algebra) , graphic matroid , graph , topology (electrical circuits) , mechanical engineering , engineering
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 q ∈ R such that every signed graph G that admits a nowhere‐zero integer flow has a signed circuit cover of total length at most q · | E ( G ) | . We show that if G is bridgeless, then q ≤ 9 , and in the general case q ≤ 11 .