# G+--的平面性The Planarity of G+--

• 全文下载: PDF(1577KB)    PP.237-242   DOI: 10.12677/AAM.2018.73029
• 下载量: 528  浏览量: 650

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.

1. 引言

2. 证明

$G\in \left\{{C}_{3},{C}_{3}+{K}_{1},{P}_{4},{P}_{4}+{K}_{1},{P}_{3}+{K}_{2},{P}_{3}+{K}_{2}+{K}_{1},{K}_{1,3},{K}_{1,3}+{K}_{1},3{K}_{2},3{K}_{2}+{K}_{1},3{K}_{2}+2{K}_{1}\right\}$ .

G+−−：3K2 + 2K1，P3 + K2 + K1，K1,3 + K1，C3 + K1，P4 + K1的变换图G+−−是可平面的。根据引理2.1，C3，P4，P3 + K2，K1,3，3K2，3K2 + K1的变换图G+−−也是可平面的。

Figure 1. All graphs of size 3 without isolated vertices

Figure 2. Transformation graph G+−− of 3K2 + 2K1, P3 + K2 + K1, K1,3 + K1, C3 + K1, P4 + K1

Figure 3. Transformation graph G+−− of P3 + K2 + 2K1, K1,3 + 2K1, C3 + 2K1, P4 + 2K1

Figure 4. All graphs of size 4 without isolated vertices

Figure 5. Transformation graph of some graphs of size 4

Figure 6. Transformation graph of some graphs of size 4

Figure 7. Transformation graph of some graphs of size 4

Figure 8. All graphs of size 5 without isolated vertices

[1] 1Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan, London. https://doi.org/10.1007/978-1-349-03521-2

[2] Wu, B. and Meng, J. (2001) Basic Properties of Total Transformation 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. https://doi.org/10.1017/S0305004100041657

[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. https://doi.org/10.1016/j.disc.2005.04.002

[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. https://doi.org/10.1080/03081087.2016.1202183

[8] Deng, A., Feng, M. and Kelmans, A. (2016) Adjacency Polynomials of Digraph Transformations. Discrete Applied Mathematics, 206, 15-38. https://doi.org/10.1016/j.dam.2016.01.032

[9] Deng, A., Kelmans, A. and Meng, J. (2013) Laplacian Spectra of Regular Graph Transformations. Discrete Applied Mathematics, 161, 118-133. https://doi.org/10.1016/j.dam.2012.08.020

[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. https://doi.org/10.1016/j.disc.2007.09.040

[12] Yi, L. and Wu, B. (2009) The Transformation Graph G++−. Australasian Journal of Combinatorics, 44, 37-42.

[13] Zhen, L. and Wu, B. (2013) Hamiltonicity of Transformation Graph G+−−. Ars Combinatoria, 108, 117-127.

 [1] 1Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan, London. https://doi.org/10.1007/978-1-349-03521-2 [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. https://doi.org/10.1017/S0305004100041657 [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. https://doi.org/10.1016/j.disc.2005.04.002 [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. https://doi.org/10.1080/03081087.2016.1202183 [8] Deng, A., Feng, M. and Kelmans, A. (2016) Adjacency Polynomials of Digraph Transformations. Discrete Applied Mathematics, 206, 15-38. https://doi.org/10.1016/j.dam.2016.01.032 [9] Deng, A., Kelmans, A. and Meng, J. (2013) Laplacian Spectra of Regular Graph Transformations. Discrete Applied Mathematics, 161, 118-133. https://doi.org/10.1016/j.dam.2012.08.020 [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. https://doi.org/10.1016/j.disc.2007.09.040 [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.