Premium
Shorter signed circuit covers of graphs
Author(s) -
Kaiser Tomáš,
Lukot’ka Robert,
Máčajová Edita,
Rollová Edita
Publication year - 2019
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.22439
Subject(s) - eulerian path , signed graph , mathematics , combinatorics , discrete mathematics , graph , pure mathematics , lagrangian
A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere‐zero flow. We show that each flow‐admissible signed graph on m edges can be covered by signed circuits of total length at most ( 3 + 2 ∕ 3 )⋅ m , improving a recent result of Cheng et al. To obtain this improvement, we prove several results on signed circuit covers of trees of Eulerian graphs, which are connected signed graphs such that removing all bridges results in a collection of Eulerian graphs.