Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424041 | European Journal of Combinatorics | 2016 | 30 Pages |
Abstract
A signed graph is a pair (G,Σ) where G is a graph and Σ is a set of edges of G. A cycle of G is balanced if it contains an even number of edges of Σ, and unbalanced otherwise. A blocking pair of (G,Σ) is a pair of vertices {s,t} such that every unbalanced cycle intersects at least one of s or t. In this paper, we characterize when the blocking pairs of a signed graph can be represented by 2-cuts in an auxiliary graph. We discuss the relevance of this result to the problem of recognizing even cycle matroids and to the problem of characterizing signed graphs with no âK5 minor.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
B. Guenin, I. Pivotto, P. Wollan,