A characterization of projective-planar signed graphs

被引：0
|
作者：
Archdeacon, D [1 ]
Debowsky, M [1 ]
机构：
[1] Univ Vermont, Dept Math & Stat, Burlington, VT 05405 USA
来源：
DISCRETE MATHEMATICS | 2005年 / 290卷 / 2-3期
基金：
美国国家航空航天局;
关键词：
signed graphs; projective plane; Kuratowski;
D O I：
10.1016/j.disc.2004.09.007
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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. (c) 2004 Published by Elsevier B.V.
引用
收藏
页码：109 / 116
页数：8
相关论文
共 50 条
12345