李　敏

（湖北文理學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北　襄陽(yáng)441053）

一個(gè)5階圖與點(diǎn)、路、圈聯(lián)圖的交叉數(shù)

李敏

（湖北文理學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北襄陽(yáng)441053）

分別討論了5階圖G16與nK1，Pn，Cn聯(lián)圖的交叉數(shù)，得到，其中n K1是n個(gè)孤立點(diǎn)構(gòu)成的圖，Pn，Cn分別是含n個(gè)點(diǎn)的路和圈.

5階圖；交叉數(shù)；聯(lián)圖；路；圈

圖的交叉數(shù)概念起源于Turan的“磚廠問(wèn)題”，Garey和Johnson［1］已經(jīng)證明這是一個(gè)NP-完全問(wèn)題.由于解決該問(wèn)題的難度較大，迄今為止，能確定交叉數(shù)的圖類還不多，其中小階圖與路、圈、星的笛卡爾積圖是目前少數(shù)幾類已知精確交叉數(shù)的圖類之一［2-3］.已有聯(lián)圖的交叉數(shù)研究結(jié)果可見(jiàn)文獻(xiàn)［4-9］.為了進(jìn)一步豐富交叉數(shù)的結(jié)果，本文在前人研究的基礎(chǔ)上，擬探討聯(lián)圖G16+n K1，G16+Pn，G16+Cn的交叉數(shù)（圖G16［2］358的畫法如圖1所示），文中所用的概念、符號(hào)及圖的有關(guān)性質(zhì)等與文獻(xiàn)［6，10］一致.

圖1　圖G16Fig.1 The graph G16

1　聯(lián)圖G16+n K1的交叉數(shù)

圖G16+n K1是由圖G16以及n個(gè)點(diǎn)t1，t2，…，tn和G16的點(diǎn)連接而成的.記ti和G16的點(diǎn)連接而成的圖為Ti.由圖2知

命題1 設(shè)圖G16+n K1（n≥3）有一個(gè)好畫法D，圖G16+（n-2）K1在畫法D下至少有個(gè)交叉點(diǎn).如果i≠j（i，j∈｛1，2，…，n｝），使得crD（Ti，Tj）=a，crD（Ti∪Tj，G16）=b，同時(shí)對(duì)任意的k≠i，j，有crD（Ti∪Tj，Tk）≥4，則圖G16+n K1在畫法D下至少有Z（5，n）+n+ n/2+a+b-3個(gè)交叉點(diǎn).

圖2　圖G16+n K1的一個(gè)好畫法Fig.2 A drawing of G16+n K1

證明 可設(shè)crD（Ti，Tj）=a，crD（Ti∪Tj，G16）=b，同時(shí)對(duì)任意的k≠i，j，有crD（Ti∪Tj，Tk）≥4，則由圖的交叉數(shù)性質(zhì)可得

命題2 設(shè)圖G+n K有好畫法D，又存在i，對(duì)任意j≠i（i，j∈｛1，2，…，n｝），有cr（G∪Ti，

161D16Tj）≥4.若使得crD（G16∪Ti，Tj）＞4的Tj有c個(gè)，則在畫法D下圖G16+n K1至少有個(gè)交叉點(diǎn).

命題3 設(shè)圖G16+n K1有好畫法D，若存在i≠j（i，j∈｛1，2，…，n｝），使得crD（Ti，Tj）=0，則crD（G16，Ti∪Tj）≥3.

證明 由D為圖G16+n K1的好畫法及crD（Ti，Tj）=0知，在D誘導(dǎo)的Ti∪Tj的子畫法中Ti和Tj的邊與邊之間無(wú)交叉點(diǎn).對(duì)任意G16的點(diǎn)x，含有它的區(qū)域只包含G162個(gè)不同于x的點(diǎn).而由圖1知，點(diǎn)a，b，c，d的度均不小于3，因此與這4點(diǎn)相連的邊上至少有3個(gè)交叉點(diǎn)，結(jié)論成立.

證明 當(dāng)n=1時(shí)，由圖2知cr（G16+K1）≤1，又因K5是圖G16+K1的子圖，故cr（G16+K1）≥1，即有cr（G16+K1）=1.當(dāng)n=2時(shí)，由圖2知cr（G16+2K1）≤3.下面證明反向不等式cr（G16+ 2K1）≥3.可證G16（在同構(gòu)意義下）只有如圖3所示的7種畫法.若存在Ti（i=1，2），滿足crD（G16，Ti）=0，則G16∪Ti只有如圖4所示的2種畫法，可證無(wú)論tj落入何區(qū)域，均有crD（G16∪Ti，Tj）≥3.若對(duì)任意的Ti，有crD（G16，Ti）≠0，則crD（G16，T1∪T2）≥2.如果crD（T1，T2）=0，則由命題3知crD（G16，T1∪T2）≥3；如果crD（T1，T2）≠0，則crD（T1∪T2）≠0.又因crD（G16+2K1）=crD（G16∪T1∪T2）=crD（G16）+crD（G16，T1∪T2）+crD（T1∪T2），故在上述幾種情形下都有cr（G16+2K1）≥3，即結(jié)論成立.

圖3　圖G16在同構(gòu)意義下的所有畫法Fig.3 The drawings of G16in the isomorphism sense

情形1：有Ti和Tj，滿足crD（Ti，Tj）=0.由命題3知crD（G16，Ti∪Tj）≥3.又因cr（K5，3）=4，故有crD（Ti∪Tj， Tk）≥4（對(duì)任意的k≠i，j），由命題1知，這與（2）式矛盾.

圖4　圖G16∪Ti滿足crD（G16，Ti）=0的所有可能子畫法Fig.4 The possible subdrawings of G16∪Tiwith crD（G16，Ti）=0

情形2：對(duì)任意的Ti，Tj（i，j∈｛1，2，…，n｝），滿足crD（Ti，Tj）≥1.

1）若有i≠j，使得crD（Ti，Tj）=1，則由圖3知crD（G16∪Ti，Tj）≥3.若crD（G16∪Ti，Tj）≥4，則由命題2知，這與（2）式矛盾.若crD（G16∪Ti，Tj）=3，則G16∪Ti∪Tj的所有可能畫法如圖5所示.

在圖5中，運(yùn)用計(jì)數(shù)方法可知，對(duì)任意的k≠i，j，當(dāng)tk位于區(qū)域ω 之外時(shí)，為保證對(duì)任意的i≠j，有crD（Ti，Tj）≥1，可得crD（G16∪Ti∪Tj，Tk）≥6，則由圖的交叉數(shù)的性質(zhì)得，這與（2）式矛盾.

圖5　當(dāng)crD（Ti，Tj）=1，crD（G16∪Ti，Tj）=3時(shí)，圖G16∪Ti∪Tj的所有可能畫法Fig.5 The possible subdrawings of G16∪Ti∪Tjwith crD（Ti，Tj）=1 and crD（G16∪Ti，Tj）=3

當(dāng)tk位于區(qū)域ω 時(shí)，有crD（G16∪Ti∪Tj，Tk）≥5，故只須討論存在tk使得crD（G16∪Ti∪Tj，Tk）=5的情況.

當(dāng)tk位于圖5（a）中ω 區(qū)域時(shí)，當(dāng)且僅當(dāng)crD（G16，Tk）=0時(shí)crD（G16∪Ti∪Tj，Tk）=5才成立，故可得crD（Ti∪Tj，Tk）=5.又由圖5（a）知，crD（Ti∪Tj，G16）=2，故由命題1知，這與（2）式矛盾.

當(dāng)tk位于圖5（b）（c）（d）中ω 區(qū)域時(shí)，在相應(yīng)的圖G16∪Ti∪Tj∪Tk中計(jì)數(shù)可得crD（G16∪Ti∪Tj∪Tk，Tl）≥7.若對(duì)任意的l≠i，j，k，有crD（G16∪Ti∪Tj∪Tk，Tl）≥8，則同上分析可得與（2）式矛盾.若存在l，使得crD（G16∪Ti∪Tj∪Tk，Tl）=7（當(dāng)tk位于圖5（b）和（c）中一個(gè)特定區(qū)域時(shí)會(huì)出現(xiàn)這種情況），則繼續(xù)計(jì)數(shù)，可得對(duì)任意的m≠i，j，k，l，有crD（G16∪Ti∪Tj∪Tk∪Tl，Tm）≥10，同上分析可得與（2）式矛盾.

2）對(duì)任意的Ti，Tj（i，j∈｛1，2，…，n｝），滿足crD（Ti，Tj）≥2.由假設(shè)知，對(duì)任意的k≠i，j，有crD（Ti∪Tj，Tk）≥4.若i≠j，使得crD（Ti，Tj）=2，則由圖3知crD（G16，Ti∪Tj）≥1；若對(duì)任意的i≠j，有crD（Ti，Tj）≥3，則由命題1知，這2種情形下都有crD（G16+n K1）≥Z（5，n）+n+n/2，此與（2）式矛盾.定理1證畢.

2　聯(lián)圖G16+Pn的交叉數(shù)

在圖G16+n K1中通過(guò)連接點(diǎn)t1，t2，…，tn構(gòu)成路Pn可得圖G16+Pn，故有

證明 由于圖G16+n K1是G16+Pn的子圖，故根據(jù)圖的交叉數(shù)的性質(zhì)［6］208和定理1，有

在圖2中，連接點(diǎn)t1，t2，…，tn形成路Pn時(shí)可令其僅與G16的邊cd 相交，即可得下面假設(shè)圖G16+Pn有好畫法D，使得

情形1：存在Ti（i∈｛1，2，…，n｝），使得crD（G16，Ti）=0.

若設(shè)crD（G16，Ti）=0，則G16∪Tn只有2種畫法（如圖4所示）.

1）當(dāng)ti（i∈｛1，2，…，n-1｝）位于圖4中除δ1，δ2外的任何含tn的區(qū)域時(shí)，因它最多只可能含G16的2個(gè)點(diǎn)且與它相鄰的區(qū)域只含3個(gè)頂點(diǎn)在邊界上，因此crD（G16∪Tn，Ti）≥4，于是，矛盾.

2）當(dāng)ti（i∈｛1，2，…，n-1｝）位于δ1或δ2時(shí)，有crD（G16∪Tn，Ti）≥3，crD（G16）=1.若對(duì)任意的Ti（i∈｛1，2，…，n-1｝），有crD（G16∪Tn，Ti）≥4，則由情形1之1）知，矛盾.若存在Ti使得crD（G16∪Tn，Ti）=3，不妨設(shè)i=n-1，則可得crD（G16∪Tn-1∪Tn）≥4，crD（G16，Tn-1）=0.又因路Pn的邊上無(wú)交叉點(diǎn)，故由圖4（a）知crD（Tk，G16∪Tn-1∪Tn）≥7（k∈｛1，…，n-2｝）.同上分析可得，這與（5）式矛盾.

情形2：對(duì)任意Ti（i∈｛1，2，…，n｝），有crD（G16，Ti）≥1.

由cr（G16+2K1）=3知crD（G16∪Tn-1∪Tn）≥3.又因路Pn的邊上無(wú)交叉點(diǎn)，故可得crD（Tk，G16∪Ti∪Tj）≥7，k≠i，j.由情形1之2）知，這與（5）式矛盾.定理2證畢.

3　聯(lián)圖G16+Cn的交叉數(shù)

圖G16+Cn可以通過(guò)在圖G16+n K1中連接點(diǎn)t1，t2，…，tn形成圈Cn而得到，故有由于5K1+Cn是圖G16+Cn的子圖，記Tx為G16的點(diǎn)x 與點(diǎn)t1，t2，…，tn相連而成的圖，因此

證明 在圖2中，當(dāng)連接t1，t2，…，tn構(gòu)成圈Cn時(shí)它可以僅與G16的邊交叉3次，即得下證反向不等式.假設(shè)存在好畫法D，使得，則由定理1，2知，Cn邊上最多只有2個(gè)交叉點(diǎn).

若crD（Cn）=0，則當(dāng)crD（G16，Cn）=0且crD（Tx，Cn）=0（x∈｛a，…，e｝）時(shí)，G16+Cn在D下至少有個(gè)交叉點(diǎn)［4］166.當(dāng)某個(gè)crD（Tx，Cn）≥1時(shí)，由crD（G16，Cn）=0得，此時(shí)G16+ Cn至少有個(gè)交叉點(diǎn).當(dāng)crD（G16，Cn）≥1時(shí)，由前述假設(shè)Cn邊上最多只有2個(gè)交叉點(diǎn)得，邊ce和Cn交叉，故G16+Cn至少有個(gè)交叉點(diǎn).這些結(jié)論都與假設(shè)矛盾.

若crD（Cn）≠0，此時(shí)所有Tx（x∈｛a，…，e｝）在Cn的那個(gè)包含t1，t2，…，tn的區(qū)域內(nèi)，則G16+Cn在D下至少有個(gè)交叉點(diǎn)，這與假設(shè)矛盾.證畢.

［1］GAREY M R，JOHNSON D S.Crossing number is NP-complete［J］.SIAM J Alg Discrete Meth，1983，4（3）：312-316.

［6］周志東，黃元秋，彭小多，等.一個(gè)小圖與路和圈的聯(lián)圖的交叉數(shù)［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2013，33（2）：206-216.

［8］王晶，黃元秋.Sm∨Pn與Sm∨Cn的交叉數(shù)［J］.數(shù)學(xué)進(jìn)展，2011，40（5）：631-636.

［9］黃元秋，王晶.圖的交叉數(shù)綜述［J］.華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2010（3）：68-80.

［10］BONDY J A，MURTY U S R.Graph theory with applications［M］.London：Macmillan，1976：1-12.

The crossing numbers of the join of a 5-vertex graph with vertex，path and cycle

LI Min
（Sch of Math&Comput Sci，Hubei Univ of Arts&Sci，Xiangyang 441053，China）

This paper discusses the crossing numbers of the ioin of n K1，Pnand Cnwith a 5-vertex graph G16，i.e.，，，，n≥3，where n K1denotes n isolated vertices，while Pnand Cnare the path and cycle on n vertices，respectively.

5-vertex graph；crossing number；ioin；path；cycle

O 157.5

A 1007-824X（2015）01-0004-05

（責(zé)任編輯 秋 實(shí)）

2013-12-03.E-mail：fyi020512@126.com.

湖北省自然科學(xué)基金資助項(xiàng)目（2012FFC053）.

李敏.一個(gè)5階圖與點(diǎn)、路、圈聯(lián)圖的交叉數(shù)［ J］.揚(yáng)州大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，18（1）：4-8.