Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.dam.2017.10.002 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Signed graph,Signed circuit,Circuit cover,Minimum circuit cover | Discrete mathematics,Graph,Combinatorics,Signed graph,Integer flow,Balanced circuit,Bidirected graph,Electronic circuit,Mathematics | Journal |
Volume | ISSN | Citations |
235 | 0166-218X | 1 |
PageRank | References | Authors |
0.35 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jing Chen | 1 | 285 | 60.83 |
| Genghua Fan | 2 | 412 | 65.22 |