G^+--的平面性

The Planarity of G^+--

对于一个简单图G,变换图G+??定义为 ,且两个顶点 相邻当且仅当满足下列三个条件:1) 并且 ,2) 并且 在G 中不相邻,3) x和y,其中一个在 中,另一个在 中,并且它们在G中关联。在这篇文章里,我们将证明G+??是平面的当且仅当 或者与下列的某个图同构:C3,C3 + K1,P4,P4 + K1,P3 + K2,P3 + K2 + K1,K1,3,K1,3 + K1,3K2,3K2 + K1,3K2 + 2K1,C4,C4 + K1,2P3。

Let G be a simple graph. The transformation graph  of G is the graph with vertex set  in which the vertex x and y are joined by an edge if and only if the following condi-tion holds: 1)  and x and y are adjacent in G, 2) , and x and y are not adjacent in G, 3) one of x and y is in V(G) and the other is in E(G), and they are not incident in G. In this paper, it is shown that G+?? is planar if and only if  or G is isomorphic to one of the following graphs: C3, C3 + K1, P4, P4 + K1, P3 + K2, P3 + K2 + K1, K1,3, K1,3 + K1, 3K2, 3K2+ K1, 3K2 + 2K1, C4, C4 + K1, 2P3.