G+--的平面性
The Planarity of G+--
DOI: 10.12677/AAM.2018.73029, PDF,   
作者: 王 丹：新疆大学，数学与系统科学学院，新疆 乌鲁木齐；刘晓平：新疆工程学院，新疆 乌鲁木齐
关键词: 全图；平面性；变换图；Total Graph； Planarity； Transformation Graph
摘要: 对于一个简单图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。
Abstract: 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.
文章引用：王丹, 刘晓平. G+--的平面性[J]. 应用数学进展, 2018, 7(3): 237-242. https://doi.org/10.12677/AAM.2018.73029

参考文献

[1] 1Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan, London.
[Google Scholar] [CrossRef] 
[2] Wu, B. and Meng, J. (2001) Basic Properties of Total Trans-formation Graphs. Journal of Mathematical Study, 34, 109-116.
[3] Behzad, M. (1967) A Criterion for the Planarity of the Total Graph of a Graph. Mathematical Proceedings of the Cambridge Philosophical Society, 63, 679-681.
[Google Scholar] [CrossRef] 
[4] Liu, X. (2006) On the Planarity of G−−−. Journal of Xinjiang University (Science & Engineering), 23, 159-161.
[5] Wu, B., Zhang, L. and Zhang, Z. (2005) The Trnasformation Graph Gxyz When x, y, z  {+, −}. Discrete Mathematics, 296, 263-270.
[Google Scholar] [CrossRef] 
[6] Chen, J., Huang, L. and Zhou, J. (2012) Super Connectivity and Super Edge-Connectivity of Transformation Graphs G+−+. Ars Combinatoria, 105, 103-115.
[7] Deng, A. and Kelmans, A. (2017) Laplacian Spectra of Digraph Transformations. Linear and Multilinear Algebra, 65, 699-730.
[Google Scholar] [CrossRef] 
[8] Deng, A., Feng, M. and Kelmans, A. (2016) Adjacency Polynomials of Digraph Transformations. Discrete Applied Mathematics, 206, 15-38.
[Google Scholar] [CrossRef] 
[9] Deng, A., Kelmans, A. and Meng, J. (2013) Laplacian Spectra of Regular Graph Transformations. Discrete Applied Mathematics, 161, 118-133.
[Google Scholar] [CrossRef] 
[10] Li, J. and Liu, J. (2014) Some Basic Properties of a Class of Total Transformation Digraphs. Ars Combinatoria, 116, 205-211.
[11] Xu, L. and Wu, B. (2008) Transformation Graph G−+−. Discrete Mathematics, 308, 5144-5148.
[Google Scholar] [CrossRef] 
[12] Yi, L. and Wu, B. (2009) The Transformation Graph G++−. Aus-tralasian Journal of Combinatorics, 44, 37-42.
[13] Zhen, L. and Wu, B. (2013) Hamiltonicity of Transformation Graph G+−−. Ars Combinatoria, 108, 117-127.

为你推荐