摘要
图G的变换图G--+以V(G)∪E(G)为其顶点集,对任意的α,β∈V(G)∪E(G),α和β在图G--+中邻接的条件如下:(i)α,β∈V(G),且α和β在G中不相邻,(ii)α,β∈E(G),且α和β在G中不相邻,(iii)α∈V(G),β∈E(G),且它们在G中相关.本文主要证明除了12个图外,G--+都不是可平面图,以及对于图G,G--+≌Pn--+当且仅当G≌Pn.
The transformation graph G --＋ of G is the graph with vertex set V（G）∪E（G） in which the vertex α and β are joined by an edge if one of the following conditions holds：（i） α,β∈V（G）,and α and β are not adjacent in G,（ii） α,β∈E（G）,and α and β are not adjacent in G,（iii） α∈V（G）,β∈E（G）,and they are incident in G. In this paper,it is shown that G --＋ is not planar except for 12 graphs. It is also shown that for a graph G,G --＋≌P n --＋ if and only if G≌P n.
出处
《南京师大学报（自然科学版）》
CAS
CSCD
北大核心
2009年第3期12-14,18,共4页
Journal of Nanjing Normal University(Natural Science Edition)
基金
国家自然科学基金(10671095)资助项目
关键词
变换图
可平面图
同构
transformation graph
planar graph
isomorphism
