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

李　敏

（湖北文理學院數(shù)學與計算機科學學院，湖北　襄陽441053）

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

李敏

（湖北文理學院數(shù)學與計算機科學學院，湖北襄陽441053）

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

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

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

圖1　圖G16Fig.1 The graph G16

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

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

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

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

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

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

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

命題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誘導的Ti∪Tj的子畫法中Ti和Tj的邊與邊之間無交叉點.對任意G16的點x，含有它的區(qū)域只包含G162個不同于x的點.而由圖1知，點a，b，c，d的度均不小于3，因此與這4點相連的邊上至少有3個交叉點，結(jié)論成立.

證明 當n=1時，由圖2知cr（G16+K1）≤1，又因K5是圖G16+K1的子圖，故cr（G16+K1）≥1，即有cr（G16+K1）=1.當n=2時，由圖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種畫法，可證無論tj落入何區(qū)域，均有crD（G16∪Ti，Tj）≥3.若對任意的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（對任意的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：對任意的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中，運用計數(shù)方法可知，對任意的k≠i，j，當tk位于區(qū)域ω 之外時，為保證對任意的i≠j，有crD（Ti，Tj）≥1，可得crD（G16∪Ti∪Tj，Tk）≥6，則由圖的交叉數(shù)的性質(zhì)得，這與（2）式矛盾.

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

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

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

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

2）對任意的Ti，Tj（i，j∈｛1，2，…，n｝），滿足crD（Ti，Tj）≥2.由假設(shè)知，對任意的k≠i，j，有crD（Ti∪Tj，Tk）≥4.若i≠j，使得crD（Ti，Tj）=2，則由圖3知crD（G16，Ti∪Tj）≥1；若對任意的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中通過連接點t1，t2，…，tn構(gòu)成路Pn可得圖G16+Pn，故有

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

在圖2中，連接點t1，t2，…，tn形成路Pn時可令其僅與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）當ti（i∈｛1，2，…，n-1｝）位于圖4中除δ1，δ2外的任何含tn的區(qū)域時，因它最多只可能含G16的2個點且與它相鄰的區(qū)域只含3個頂點在邊界上，因此crD（G16∪Tn，Ti）≥4，于是，矛盾.

2）當ti（i∈｛1，2，…，n-1｝）位于δ1或δ2時，有crD（G16∪Tn，Ti）≥3，crD（G16）=1.若對任意的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的邊上無交叉點，故由圖4（a）知crD（Tk，G16∪Tn-1∪Tn）≥7（k∈｛1，…，n-2｝）.同上分析可得，這與（5）式矛盾.

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

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

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

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

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

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

若crD（Cn）≠0，此時所有Tx（x∈｛a，…，e｝）在Cn的那個包含t1，t2，…，tn的區(qū)域內(nèi)，則G16+Cn在D下至少有個交叉點，這與假設(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］周志東，黃元秋，彭小多，等.一個小圖與路和圈的聯(lián)圖的交叉數(shù)［J］.系統(tǒng)科學與數(shù)學，2013，33（2）：206-216.

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

［9］黃元秋，王晶.圖的交叉數(shù)綜述［J］.華東師范大學學報：自然科學版，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

（責任編輯 秋 實）

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

湖北省自然科學基金資助項目（2012FFC053）.

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