G^+--的平面性

The Planarity of G^+--

摘要: 对于一个简单图G，变换图G⁺⁻⁻定义为 ，且两个顶点 相邻当且仅当满足下列三个条件：1)  并且 ，2)  并且 在G 中不相邻，3) x和y，其中一个在 中，另一个在 中，并且它们在G中关联。在这篇文章里，我们将证明G+−−是平面的当且仅当 或者与下列的某个图同构：C₃，C₃ + K₁，P₄，P₄ + K₁，P₃ + K₂，P₃ + K₂ + K₁，K_1,3，K_1,3 + K₁，3K₂，3K₂ + K₁，3K₂ + 2K₁，C₄，C₄ + K₁，2P₃。

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: C₃, C₃ + K₁, P₄, P₄ + K₁, P₃ + K₂, P₃ + K₂ + K₁, K_1,3, K_1,3 + K₁, 3K₂, 3K₂+ K₁, 3K₂ + 2K₁, C₄, C₄ + K₁, 2P₃.

1. 引言

这篇文章里所有的图都是有限的，简单的，无向的。在 [1] 中可以找到没有被定义的术语和符号。图 $G=\left(V\left(G\right)\cup E\left(G\right)\right)$ ， $\left|V\left(G\right)\right|$ 是G的顶点的个数， $\left|E\left(G\right)\right|$ 是G的边的个数，v的邻集N_G(v)是G中所有与v相邻的顶点的集合。因为G是简单图，所以有 $\left|N_G\left(v\right)\right|=d_G\left(v\right)$ 。

假设V'是V(G)的一个非空子集。图G的导出子图 $G\left[V^{\prime }\right]$ 定义为 $V\left(G\left[V^{\prime }\right]\right)=V^{\prime }$ 并且 $uv\in E\left(G\left[V^{\prime }\right]\right)$ 当且仅当 $uv\in E\left(G\right)$ 。两个图 $G=\left(V\left(G\right),E\left(G\right)\right)$ ， $H=\left(V\left(H\right),E\left(H\right)\right)$ 的并，记为 $G\cup H$ ，点集是 $V\left(G\right)\cup V\left(H\right)$ ，边集是 $E\left(G\right)\cup E\left(H\right)$ 。如果它们不交，即 $V\left(G\right)\cap V\left(H\right)=\varnothing$ ，它们的并记为G + H。

图G的线图L(G)的点集是E(G)，其两个顶点相邻当且仅当它们在G中相邻。图G的全图G⁺⁺⁺，它的点集是 $V\left(G\right)\cup E\left(G\right)$ ，任意两点相邻当且仅当它们在G中或者是相邻的，或者是关联的。吴和孟 [2] 推广了全图的概念，并且引入了一些新的变换图。我们也采用了G^xyz这个符号， $x,y,z\in \left\{+,-\right\}$ ，这个符号是在 [2] 中被引入的。

如果一个图可以在平面中画出来使得他们的边不交，只有在端点处相交，我们就说这个图在平面上是可嵌入的，或者是可平面的。图G的剖分是在G的边上插入一系列的点之后得到的。Behzad [3] 刻画了图G的变换图G⁺⁺⁺是可平面的。刘 [4] 给出了图G的变换图G⁻⁻⁻是可平面的充要条件。吴等 [5] 证明了图G的变换图G⁻⁺⁺可平面的充要条件是G点数至多为4。读者可参考 [6] - [13] 了解更多的关于图G^xyz的结论。按习惯，n个顶点的完全图，圈，路分别记为K_n，C_n，P_n。两部分中的顶点数分别为m，n的完全二部图记为K_m,n。

文章的第二部分我们使用了著名的Kuratowski [1] 定理。

定理1.1：一个图是可平面的当且仅当它不包含K₅或者K_3,3的剖分。

推论1.2：每个可平面简单图都有一个顶点的度数至多为5。

下面是这篇文章的主要结论。

定理1.3：对于一个边数为m的图G，G⁺⁻⁻是可平面的当且仅当m ≤ 2或者G与下面的某个图同构：C₃，C₃ + K₁，P₄，P₄ + K₁，P₃ + K₂，P₃ + K₂ + K₁，K_1,3，K_1,3 +K₁，3K₂，3K₂ + K₁，3K₂ + 2K₁，C_4，C₄ + K₁，2P₃。

证明：由引理2.1~2.5的结论可以立即得到。

2. 证明

下面的结论容易证明，但很有用。

引理2.1：如果H是G的子图，那么H⁺⁻⁻是G⁺⁻⁻的子图。

由引理2.1，如果H⁺⁻⁻是非可平面的， $G=H+k{K}_1$ ，k是一个整数，并且k ≥ 1，那么G⁺⁻⁻是非可平面的。我们很容易检测到对于边数m ≤ 2的图，G⁺⁻⁻是非可平面的。接下来我们考虑边数为3的图，在图1中我们精确地给出了所有边数为3的并且没有孤立点的5个图。

引理2.2：对于一个边数为3的图G，G⁺⁻⁻是可平面的当且仅当

$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,3K_2,3K_2+K_1,3K_2+2K_1\right\}$ .

证明：充分性：正如图2中所示：

G⁺⁻⁻：3K₂ + 2K₁，P₃ + K₂ + K₁，K_1,3 + K₁，C₃ + K₁，P₄ + K₁的变换图G⁺⁻⁻是可平面的。根据引理2.1，C₃，P₄，P₃ + K₂，K_1,3，3K₂，3K₂ + K₁的变换图G⁺⁻⁻也是可平面的。

必要性：对于每一个图 $G\in \left\{P_3+K_2+2K_1,K_{1,3}+2K_1,C_3+2K_1,P_4+2K_1\right\}$ ，其变换图 ${\left(G+2K_1\right)}^{+}{}^{--}$ 是非可平面的，因为它们都包含K_3,3的剖分，如图3所示。

Figure 1. All graphs of size 3 without isolated vertices

图1. 所有边数为3的没有孤立点的图

Figure 2. Transformation graph G⁺⁻⁻ of 3K₂ + 2K₁, P₃ + K₂ + K₁, K_1,3 + K₁, C₃ + K₁, P₄ + K₁

图2. 3K₂ + 2K₁，P₃ + K₂ + K₁，K_1,3 + K₁，C₃ + K₁，P₄ + K₁的变换图G⁺⁻⁻

Figure 3. Transformation graph G⁺⁻⁻ of P₃ + K₂ + 2K₁, K_1,3 + 2K₁, C₃ + 2K₁, P₄ + 2K₁

图3. P₃ + K₂ + 2K₁，K_1,3 + 2K₁，C₃ + 2K₁，P₄ + 2K₁的变换图G⁺⁻⁻

Figure 4. All graphs of size 4 without isolated vertices

图4. 所有边数为4的没有孤立点的图

Figure 5. Transformation graph of some graphs of size 4

图5. 一些边数为4的变换图

Figure 6. Transformation graph of some graphs of size 4

图6. 一些边数为4的变换图

现在我们来考虑边数为4的图，我们精确地给出了11种边数为4的没有孤立点的图，如图4所示。

引理2.3：对于一个边数为4的图G，G⁺⁻⁻是可平面的当且仅当 $G\in \left\{C_4,C_4+K_1,2P_3\right\}$ 。

证明：充分性：在图6和图7中我们给出了 ${\left(C_4+K_1\right)}^{+--}$ ， ${\left(2P_3\right)}^{+--}$ 平面嵌入，因此 ${\left(C_4+K_1\right)}^{+--}$ ， ${\left(2P_3\right)}^{+--}$ 是可平面的，由引理2.1， ${\left(C_4\right)}^{+--}$ 也是可平面的。

必要性：设G是一个边数为4的图，那么G可以由图4增加一些孤立点得到，由图4~图7和引理2.1，如果 $G\notin \left\{C_4,C_4+K_1,2P_3\right\}$ ，G⁺⁻⁻是非可平面的。

现在我们来考虑边数为5的图。我们精确地给出了边数为5的没有孤立点的图，如图8所示。

引理2.4：对于边数为5的图G，其变换图G⁺⁻⁻是非可平面的。

证明：因为图G是一个边数为5的图(如图8所示)，G包含一个边数为4的子图H，不同构于 $C_4,C_4+K_1,2P_3$ 。由引理2.3，H⁺⁻⁻是非平面图。又由引理2.1知，H⁺⁻⁻是G⁺⁻⁻的子图。所以，G⁺⁻⁻也是非平面的。

引理2.5：如果图G的边数m ≥ 6，那么G⁺⁻⁻是非可平面的。

Figure 7. Transformation graph of some graphs of size 4

图7. 一些边数为4的变换图

Figure 8. All graphs of size 5 without isolated vertices

图8. 所有边数为5的没有孤立点的图

证明：显然，G包含一个边数为5的子图H，由引理2.1得到H⁺⁻⁻是G⁺⁻⁻的子图。更进一步，由引理2.4得到G⁺⁻⁻是非可平面的。

参考文献

[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 G^xyz 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.