Article ID Journal Published Year Pages File Type
9513612 Discrete Mathematics 2005 8 Pages PDF
Abstract
A signed graph has a plus or minus sign on each edge. A simple cycle is positive or negative depending on whether it contains an even or odd number of negative edges, respectively. We consider embeddings of a signed graph in the projective plane for which a simple cycle is essential if and only if it is negative. We characterize those signed graphs that have such a projective-planar embedding. Our characterization is in terms of a related signed graph formed by considering the theta subgraphs in the given graph.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,