一些交叉数为2的特殊联图

王晶，雷宝，吕美，汤琼枝

(长沙学院 计算机工程与应用数学学院，湖南 长沙，410003)

在接下来的讨论中，仅考虑简单图未说明的概念和术语均同文献[1]。令G为图，其顶点集和边集分别为V(G)和E(G)，其中用v(G)表示G中的顶点数目。

两个点不相交的图G1和G2的联图，用G1∨G2表示，是在G1和G2的并图中，把G1的每个顶点和G2的每个顶点连接起来所得到的图。Pn和Cn分别表示顶点数为n的路和圈。星图Sn表示完全二部图K1，n。图1和图2列出了所有阶数为3和4的图。

图1 所有的3-阶图Fig.1 All graphs of order 3

图2 所有的4-阶图Fig.2 All graphs of order 4

一个图G画在平面上，若满足如下条件：

1)任何两条相交叉的边最多交叉一次。2)边不能自身相交。3)有相同端点的两条边不交叉。4)没有三条边交叉于同一个点。

根据交叉数的定义，容易得出

性质1 给定图G和H，若图G是图H的子图，则cr(G)≤cr(H)。

GAREY等[2]已经证明了确定图的交叉数是一个NP-完全问题，因此，计算图的交叉数是十分困难的。由于问题的难度大，目前关于此方面的研究结果甚少，目前仅对于如完全图、笛卡尔积图、循环图、联图等特殊图类，确定了他们的交叉数，见文献[3-10]等。

目前，有关图的交叉数研究，还可以从另一个方向着手，即结合图的交叉数来刻画图的结构特征。KLESC等[11-12]从笛卡尔积图这种特殊情形着手，开始这方面的研究，得到了当cr(G1□G2)≤2时，因子图G1和G2满足的条件。对于联图，KULLI等在文献[13]中刻画了其交叉数为0时的结构特征。交叉数为1的联图G1∨G2的充要条件已经被刻画[14]。当cr(G1∨G2)≤2时，刻画了因子图G1和G2的充要条件，主要结果如下：

定理1 设G1和G2为图，v(G1)=3，则cr(G1∨G2)=2当且仅当G1和G2为如下情形之一：

1 一些引理

引理1[7-8]对于min{m，n}≤6，有cr(Pm∨Pn)=Z(m，n)，cr(Pm∨Cn)=Z(m，n)+1，cr(Cm∨Cn)=Z(m，n)+2。

图3 F1∨C4的一个好画法Fig.3 A good drawing ofF1∨C4

图4 C3∨F4的一个好画法Fig.4 A good drawing of C3∨F4

引理2cr(F1∨C4)=2。

证明：首先，图3给出了F1∨C4交叉数为2的一个好画法，根据交叉数的定义，很容易得到cr(F1∨C4)≤2。另一方面，由于F1∨C4包含完全二部图K3，4作为子图，根据性质1，所以crF1∨C4≥crK3，4=2[15]。因此有cr(F1∨C4)=2成立。

证明：对于上述图，一方面发现它们都包含K3，4作为子图，另一方面它们又都是F1∨C4的子图，因此结合性质1和引理2，能够得到此引理成立。

引理6 令G1是任意的3-阶图，则cr(G1∨F5)≥3。

引理8 对于i∈{5，6，7}，有cr(P3∨Fi)≥3。另外，cr(P3∨C4)≥3，cr(P3∨S3)≥3，cr(P3∨K4)≥3。

证明：对于i∈5，6，7，由于P3∨Fi包含子图F1∨Fi，根据引理5和引理6，所以cr(P3∨Fi)≥3。

由引理1可得cr(P3∨C4)≥3成立。最后，根据F1是P3的子图以及引理5可得cr(P3∨S3)≥3且cr(P3∨K4)≥3。证毕。

引理10 对于i∈{3，5，6，7}，有cr(C3∨Fi)≥3。

另外，cr(C3∨P4)≥3，cr(C3∨C4)≥3，cr(C3∨S3)≥3，cr(C3∨K4)≥3。

证明：首先，结合网站http：∥crossing.uos.de/上的计算机程序，可以计算得出cr(C3∨F3)=3。

其次，根据P3是C3的子图，结合性质1、引理1及引理8，不难得出引理成立，证毕。

引理11 令G1和G2都是3阶图，除了cr(P3∨C3)以外，其余都有cr(G1∨G2)≠2。

图5 F1∨C3的一个好画法Fig.5 A good drawing of F1∨C3

证明：根据引理1，可以得到cr(P3∨C3)=2，cr(P3∨P3)=1和cr(C3∨C3)=3。图5给出了F1∨C3的一个交叉数为1的好画法，根据交叉数的定义容易得到cr(F1∨C3)≤1。

而对于其余的3-阶图G1和G2，根据图1，可以发现所有的G1∨G2要么是P3∨P3的子图，要么是F1∨C3的子图，因此根据性质1有cr(G1∨G2)≤cr(P3∨P3)=1，或者cr(G1∨G2)≤cr(F1∨C3)≤1。证毕。

2 定理1的证明

定理1的证明 首先，若G1和G2满足情形(1)、(2)、(3)或(4)，则根据引理1、2、3及引理11，可得cr(G1∨G2)=2。下面，只需证明除了上述四种情况之外没有别的因子图G1和G2满足cr(G1∨G2)=2。

在此情形下，一方面能够得出v(G2)≤4，否则G1∨G2包含子图K3，5，而其交叉数cr(K3，5)=4。另一方面，由于cr(C3∨P2)=1，所以v(G2)≥3。故3≤v(G2)≤4。

子情形1.1：v(G2)=4。

根据引理3、4、5和引理6，可得G2是类型(1)的图。

子情形1.2：v(G2)=3。

情形2：G1=F1。

子情形2.1：v(G2)=4。

根据引理3、4、5和引理6可得G2是类型(2)的图。

子情形2.2：v(G2)=3。

根据引理11，对于所有的3-阶图G2都有cr(F1∨G2)≠2。

情形3：G1=P3。

子情形3.1：v(G2)=4。

子情形3.2：v(G2)=3。

根据引理11，G2必须是C3。

情形4：G1=C3。

子情形4.1：v(G2)=4。

子情形4.2：v(G2)=3。

根据引理11，G2必须是P3。