一类联图的交叉数

周志东,李龙

(衡阳师范学院 数学与统计学院,湖南 衡阳,421002)



一类联图的交叉数

周志东,李龙

(衡阳师范学院 数学与统计学院,湖南 衡阳,421002)

联图; 交叉数; 圆盘画法

性质1 令D是图G的一个好画法,且A，B，C是图G的三个互不相交的边子集,则有

(1)crD(A∪B)=crD(A)+crD(B)+crD(A,B)

(2)crD(A∪B,C)=crD(A,C)+crD(B,C)

性质3[2]设φ是Q+Cn的一个最优画法，则crφ(E(Cn))=0。

把图G在好画法D下的每一个交叉点看成一个新的顶点，则得到平面图G*和对应平面嵌入D*，我们把平面图G*在D*下的面称为图G在画法D下的域。

Jordan曲线定理[3]设J是平面上的一条Jordan曲线，平面的剩余部分被分成两个不相交的开集，称为J的内部和外部,分别记为intJ和extJ并且用IntJ和ExtJ表示它们的闭包。显然IntJ∩ExtJ=J，则连接intJ的点和extJ的点的任何连线必在某点和J相交，其中一条Jordan曲线是指一条连续的、自身不相交的、起点和终点相重合的曲线。

令G1和G2是两个点不相交的图，图G1和G2的联图G1+G2是这样的一个图:顶点集

V(G1+G2)=V(G1)∪V(G2)，边集E(G1+G2)=E(G1)∪E(G2)∪{e(u,v)|u∈V(G1)，且|v∈V(G2)}。其中，e(u,v)表示连接顶点u和v的边。

图的交叉数是图的一个重要参数,在VLSI布局，离散几何，数论，生物工程等领域都有广泛的应用。Garey和Johnson[4]证明确定图的交叉数是NP-难问题。目前，确定图类的交叉数主要集中在一些具有特殊结构的图类上，如，完全2-部图，完全3-部图，简单的图之间的笛卡尔积图，循环图以及Petersen图等。特别地，关于完全2-部图Km,n,Kleitman[5]证明了

记上式右边表达式为Z(m,n)(这里，对任意实数x,⎣x」表示不超过x的最大整数)。

M.Klesc在文献[1]中确定了路Pm，圈Cm以及阶数不超过4的简单图与路,圈的联图的交叉数,在文献[6]中确定了一个6阶图Q与n个孤立点，路Pn以及圈Cn的联图的交叉数。本文通过圆盘画法这一新途径，确定了另一个6阶图Q(见图1)与n个孤立点，路Pn以及圈Cn的联图的交叉数。

图1 6点图Q

图2 Q+nK1的一个好画法

1 引理

首先，证明几个引理。

图3 Q+K1的一个好画法

证明 当n=1时，如图3,Q+K1包含一个K3,3的子图{c,e,f;a,d,t1}，因此cr(Q+K1)=1。

而crφ(T1∪T2,Ti)≥cr(K3,6)=Z(6,3)=6，

crφ(Q∪T1∪T2)≥crφ(Q+2K1)=3，因此，

crφ(Q+nK1)≥3+6(n-2)+Z(6,n-2)+

图Q的圆盘画法:设D是一个圆盘,φ是Q的一个好画法,使得Q的所有点位于D边界,Q的所有边位于D的内部,则称φ为Q的一个圆盘D画法.在画法φ下,D的区域分成如下两种类型:

α-型区域:区域边界全部由Q的边弧组成。

β-型区域:区域边界由Q的边弧及圆盘边界弧组成。

注意:β-型区域的边界只含一段圆盘边界弧(否则Q不连通)。

引理4 设D是一个圆盘,φ是6点图Q的一个圆盘D好画法,则

(1)圆盘D的β-型区域边界最多含有Q的2个顶点,

(2)圆盘D的α-型区域边界最多含有Q的3个顶点.因此,有6个β-型区域。

证明 先证结论(1):反设β-型区域边界含有Q的顶点个数不小于3，由于β-型区域只含一段圆盘边界弧，则此时Q中必存在割点,与Q本身无割点矛盾。现分如下情形来证明结论(2):情形(1):若α-型区域边界含有Q的6个顶点的区域,易知Q中每一个点的度不大于2,矛盾。

情形(2):若α-型区域边界含有Q的5个顶点的区域,如图4所示，不妨设Q的另一个顶点x位于圆盘边界弧x1x5之间,则x只能与x1,x5相连,易导出dQ(xi)≤2(i=2,3,4)；dQ(xi)≤3(i=1,5) ，dQ(x)≤2，这与Q中有4度点矛盾。

情形(3):若α-型区域边界含有Q的4个顶点的区域,如图5所示,则圆盘边界被分成4段弧x1x2，x2x3，x3x4，x4x1,则Q的另外两个点s和t；或者位于相邻弧段上,或者位于间隔弧段上,或者同时位于同一弧段上。

图4 含有Q的5个顶点的区域

图5 含有Q的4个顶点的区域

(1)若s和t位于同一弧段上,不妨设s和t位于同一弧段x1x2上。

由于Q中点的度为2或3或4,而s和t只能与x1,x2相连,易知点x3,x4的度dQ(x3)=dQ(x4)=2，这与Q中只有一个2度点相矛盾。

(2)若s和t位于相间隔弧段上,不妨设s位于弧段x1x2上;t位于弧段x3x4上,则s只能与x1,x2相连，t只能与x3,x4相连,易知dQ(s)≤2，dQ(t)≤2 ，dQ(xi)≤3(i=1,2,3,4) 这与Q中有4度点矛盾。

(3)若s和t位于相邻的弧段上,不妨设s位于弧段x1x2上，t位于弧段x1x4上，则s只能与x1,x2相连,t只能与x1,x4相连,则易dQ(x3)≤2,dQ(s)≤2dQ(t)≤2；这与Q中只有一个点的度不超过2相矛盾。综上所述,引理4得证。

2 定理的证明

由引理1,只要考虑n≥3，反设存在Q的好画法φ使得

(1)

由引理2和3,可假定

图6 Q∪T1的限制画法

(1)若点ti落入α-型区域，由圆盘画法知此时α-型区域最多只含有Q的3个顶点且满足crφ(Ti,Tj)≥1，因此crφ(Q∪T1,Ti)≥4，且此时crφ(Q,Ti)≥3。

(2)若点ti落入β-型区域和任意细分的子区域ri(i=1,2,...,6),由于这类区域只含有Q的2个顶点,又crφ(Ti,Tj)≥1且这些区域之间至少有两个不相邻,由Jordan曲线定理有crφ(Q∪T1,Ti)≥6.设有s个ti落入α-型区域,则有n-1-s落入β-型区域和任意细分的子区域ri(i=1,2,...,6),因此

6(n-1-x)+4x+1+Z(6,n-1)=

Z(6,n-1)+6(n-1)-2x+1

(2)

由假设(1)有

2|A1|+3|A2|+|A3|≤crφ(Q,Ti)≤n+

(3)

显然,|A1|+|A2|+|A3|=n-1

(4)

由(3)(4)式可得

(5)

则有

代入(6)式有

与(1) 矛盾,从而定理证毕。

断言:在画法φ下Pn自身不相交,且crφ(Q,Pn)=0。

情形(1):区域α最多含有Q中的4个点。则对∀1≤i≤n,有crφ(Q,Ti)≥2。因此

情形(2):区域α恰好含有Q中的5个点。此时,对∀1≤i≤n,有crφ(Q,Ti)≥1，又分如下两种子情形:

图7 区域α恰含有5个点的情形

图8 区域α恰含有6个点的情形

情形(3):区域α恰含有Q中的6个顶点。

子情形(3.1):若存在一点,设为t1,使得crφ(Q,T1)=0。如图8所示:α-细分为α1,α2,α3,α4,α5,α66个区域。由Pn上无交叉点,不妨设Pn的其余所有点ti(i≥2)位于α1区域,对∀2≤i≤n,由于至少有2个领域不相邻,由Jordan曲线定理crφ(Q∪T1,Ti)≥5,且此时Q自身有1个交叉。则有

在这种情况下,crφ(Q∪T1,Ti)=4,进一步有crφ(Q,Ti)≥2，因此

(注意到n≥3)，矛盾。

(8)

断言1 图Cn自身不交叉。由性质3即得。

断言2 图Cn最多只有2个交叉。由假设即得。

情形1:crφ(Cn,Q)=0。不妨设Q的所有点和边都位于Cn的内部。

情形2:Cn与Q有相交,即crφ(Q,Cn)≠0。

由于Cn与Q都是2-连通的,因此crφ(Q,Cn)≥2,若crφ(Q,Cn)≥3，即Cn上至少有3个交叉。因此只需考虑crφ(Q,Cn)=2的情形,分如下子情形:

子情形2.2:Q中有点位于Cn的内部区域,也有点位于Cn的外部区域.

设与Cn发生交叉的这两条边为e1和e2,由此可知{e1,e2}为Q的割边集,由图Q可知,这个割边集只可能是与Q中某个2-度点关联的2条边,不妨设这个2-度点位于Cn的外部区域,则Q的其它所有点必须位于Cn的内部区域,否则由Q是连通图,2度点x0与Q中任意点有路相连,这导致Cn上至少有3个交叉。则Q中的5个点(除x0外)均与圈Cn上的n个点相连,且这些边均画在Cn围成的内部区域。由性质2有

[1]Klesc M.The join of graphs and crossing numbers[J].Electronic Notes in Discrete Mathematics ,2007,28:349-355.

[2]Tang L,Wang J,Huang Y Q.The crossing number of the join of Cnand Pn[J].International Journal Mathematical Combinatorics,2007,11:110-116.

[3]Bondy J A,Murty U S R.Graph Theory With Applications[M].Great Britain:The Macmillan Press Ltd.,1976.

[4]Garey M R,Johnson D S.Crossing number is NP-complete[J].SIAM Journal on Algebraic Discrete Methods,1993,4:312-316.

[5]Woodall D R.Cyclic-order graphs an Zarankiewicz’s crossing number conjecture[J].Journal of Graph Theory,1993,17(6):657-671.

[6]Klesc M.The crossing numbers of join of the special graph on six vertices with path and cycle[J].Discrete Mathematics,2010,310:1475-1481.

Onthecrossingnumberofthejointgraph

ZHOU Zhidong,LI Long

(Department of Mathematics and Computational Science,Hengyang Normal University，Hengyang 421002，China)

jointgraph；crossingnumber;diskcompassdrawing

1672-7010(2016)03-0016-09

2016-03-20

国家自然科学基金资助项目(11401185)；湖南省自然科学基金项目(14JJ6039)；湖南省“十三五”重点建设学科项目资助；衡阳师范学院科学启动基金(13B39)

周志东(1980—)，男，湖南邵阳人,博士，从事图论及其应用研究；E-mail:zzdongwww@163.com

O

A