Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871644 | Discrete Applied Mathematics | 2018 | 8 Pages |
Abstract
A signed graph G is a graph associated with a mapping Ï: E(G)â{+1,â1}. An edge eâE(G) is positive if Ï(e)=1 and negative if Ï(e)=â1. A circuit in G is balanced if it contains an even number of negative edges, and unbalanced otherwise. A barbell consists of two unbalanced circuits joined by a path. A signed circuit of G is either a balanced circuit or a barbell. A signed graph is coverable if each edge is contained in some signed circuit. An oriented signed graph (bidirected graph) has a nowhere-zero integer flow if and only if it is coverable. A signed circuit cover of G is a collection F of signed circuits in G such that each edge eâE(G) is contained in at least one signed circuit of F; The length of F is the sum of the lengths of the signed circuits in it. The minimum length of a signed circuit cover of G is denoted by scc(G). The first nontrivial bound on scc(G) was established by MáÄajová et al., who proved that scc(G)â¤11|E(G)| for every coverable signed graph G, which was recently improved by Cheng et al. to scc(G)â¤143|E(G)|. In this paper, we prove that scc(G)â¤256|E(G)| for every coverable signed graph G.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jing Chen, Genghua Fan,