一個五點圖和路的聯圖的交叉數

2023年12月12日發(作者：我喜歡秋天作文)

-

２０１１年１１月　汕頭大學學報（自然科學版）　第２６卷第４期　ＮＯＶ．２０１ｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｈａｎｔｏｕ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　Ｖ０Ｉ．２６　Ｎｏ．４　文章編號：１００１—４２１７（２０１１）０４　００１１—０７　一個五點圖和路的聯圖的交叉數　鄭敦勇．黃元秋　（湖南師范大學數學與計算機科學學院．湖南長沙４１００８１）　摘要：計算了一個具體圖類日　的交叉數，然后研究了一個五點圖Ｇ和　路的聯圖Ｇ　Ｖ　，　并用歸納假設法證明了這個五點圖和路的聯圖的交叉數Ｃｒ（Ｇ　Ｖ　），即當ｎ≥２時，Ｃｒ（ＣＶ　）＝４Ｌ　兒丁Ｉ兒ｌｌ　一】　ｊ．Ｊ＋Ｌ　．　Ｊ　．ｒｔ　Ｊ＋１．Ｊ　關鍵詞：圖；畫法；交叉數；聯網　中圖分類號：０　１５７．５　文獻標識碼：Ａ　Ｏ　引　言　圖的交叉數是圖的拓撲性質中一個重要的參數．研究圖的交叉數不僅具有重要的理　論意義，也具有很大的實踐意義，比如有關超大規模集成電路（ＶＬＳＩ）中的布線問題等．　然而在圖論中，計算一個圖的交叉數是很困難的．因為一般來說．找到一個圖的交叉數　的上界所對應的畫法是比較容易的．但是要證明這個畫法的交叉數即最小交叉數確實非　常困難．實際上，Ｇａｒｅｙ　Ｍ　Ｒ和Ｊｏｈｎｓｏｎ　Ｄ　Ｓｔ　１證明計算一個圖的交叉數的一般問題是個　ＮＰ—ｃｏｍｐｌｅｔｅ問題（讀者可以分別參考文獻　】中兩個比較復雜的圖的交叉數的結果）．目　前，我們僅僅知道幾類非常有限的圖的交叉數『４１，比如關于完全二部圖Ｋ　的交叉數，　Ｈａｒａｒｙ　Ｆ［５】已經證明，如果ｍ≤６，則Ｃｒ（　）＝ｚ（ｍ，ｎ），這里ｚ（ｍ，ｎ）：ｌ等兒　Ｊ　ｌ爭兒　ｊ；Ｍ　ｉ　ｎ　Ｋ１。　。［６１論述了聯圖的交叉數，并對一些特殊聯圖的交叉數給出了　證明；李波等人　證明了幾個六階圖和路　的聯圖的交叉數．本文在上述基礎上．研　究了一個五點圖和　的聯圖的交叉數．　１　基本知識　本文未做說明的概念和術語均同文獻［８】。且無特別說明時．所涉及的網均指連通簡　收稿日期：２０１０—０６—１４　作者簡介：鄭敦勇（１９８６一），男，湖南常德人，碩士．研究方向：圖論及其應用　Ｅ—ｍａｉｌ：ｚｈｅｎｇｄｕｎｙｏｎｇ０４１０２＠ｙａｈｏｏ．ｅｏｍ．ｃｌｌ；　黃元秋（１９６６一），男，湖南長沙人，教授．研究方向：圖論及其應用　基金項目：國家自然科學基金資助項目（Ｎｏ．１０７７１０６２）　ｌ２　汕頭大學學報（自然科學版）　第２６卷　單圖，用Ｖ（Ｇ）和Ｅ（Ｇ）分別表示圖的點集和邊集．圖Ｇ在曲面上的一個畫法是指把圖　Ｇ的頂點畫為曲面上的結點．把圖Ｇ的邊畫為曲面上的弧．兩條弧的公共點稱為一個交　叉．圖Ｇ在曲面上的一個畫法若滿足下列條件：ｉ）沒有任何弧自身相交；２）任何兩條弧　最多相交一次：３）相鄰的兩條弧不相交：４）沒有三條弧交于一個點．則稱此畫法為圖Ｇ　的一個好畫法．所有好畫法中對應最少的交叉數目即為圖Ｇ在該曲面上的交叉數．圖　在平面（或球面）上的交叉數稱為圖Ｇ的交叉數．記為Ｃｒ（Ｇ）．令Ｄ是圖Ｇ在平面上的　一個好畫法，則圖Ｇ在畫法Ｄ中的交叉數記為　。（Ｇ）．把每個曲面上自身不相交的封閉　個區域是指　＼　的一個分支．如果兩個區域的邊界有一條公共弧或者公共弧的片　假設Ｇ和　是兩個互不相交的圖，Ｇ　Ｖ日表示Ｇ和　的聯圖，是通過在Ｖ（Ｇ）和　曲線稱為Ｊｏｒｄａｎ曲線．且任何Ｊｏｒｄａｎ曲線把曲面一分為二［９】，所以圖Ｇ在畫法Ｄ中的　一段．稱這兩個區域是相鄰的．為了方便，把圖的畫法中的節點也稱為頂點，弧也稱為邊．　（　）之間添加邊得到的；對于　（Ｇ）ｊ＝ｍ和　（Ｈ）『＝ｎ，ＧＶ　的邊集是由Ｇ、Ｈ的邊集　和完全二部圖　…的邊集組成的『ｏＪ．　文中計算了一個具體圖類　的交叉數，并研究了五　點圖Ｇ（見圖１）和路　的聯圖Ｇ　Ｖ　，然后根據Ｈ　的畫　法和Ｇ　Ｖ　的畫法之間的一些關系，用數學歸納法證明了　Ｇ　Ｖ　的交叉數，即　Ｃｒ（Ｇｖ　）：４　Ｌ￣－Ｊ　Ｌ　Ｊ＋ｌ　＋１．　下面的等式很容易證明，將在下文經常使用：　Ｃｒ￣（Ａ　ＵＢ）：Ｃｒ￣（Ａ）＋Ｃｒｙ（Ｂ）＋ＣｒＤ（４，Ｂ）　Ｇ　圖１　Ｇ的一個好畫法　（１）　（２）　Ｃｒ￣（Ａ，ＢＵＣ）＝Ｃｒｏ（Ａ，Ｂ）＋Ｃｒ￣（Ａ，Ｃ）　其中圖４，圖Ｂ和圖Ｃ是圖中Ｅ相互不相交的子圖，Ｄ是圖Ｅ的一個好畫法　２主要結果　　，Ｋ　的５個ｎ一　用圖　表示Ｇ　ＵＫ　（Ｇ為一個五點圖）．　，　度點和Ｇ的５個頂點是相同的點；對ｉ＝１，２，…，ｎ，用ｔ　表示　中ｎ個５一度點中的一個點，并且用　表示Ｋ　，　中與　ｆＩ　點ｔ　相連的５條邊以及點ｔ　構成的子圖，見圖２，因此，有　Ｈ　：Ｇ　ｕ　５．　＝Ｇ　Ｕ（Ｕ　）　ｉ＝ｌ　（３）　圖２　的一個好畫法　定理１如果　≥１，Ｎ６－ｃ，（　）：ｚ（５，　）＋Ｌ爭Ｊ．　證明　圖３所描述的畫法顯示，　（Ｈ　）≤ｚ（５，ｎ）＋ｌ爭ｊ＝　４　ｌ爭兒旦　ｊ＋ｔｔＪ，并且如果取等號成立，則定理是對的，　所以對　進行歸納假設．當ｎ＝１和ｎ＝２時，該等式顯然是　成　的，現在假設當　≥３時，　圖３　Ｈ　的一個好畫法　第４期　鄭敦勇等：一個五點圖和路的聯圖的交叉數　ｌ３　Ｃｒ（／Ｈ４　）≥４　）≥丁兒丁Ｊ４Ｌ　Ｊｌ孚Ｊ＋ｌ＋Ｌ　Ｊ丁Ｊ　（４）　并且假設存在一個畫法Ｄ．使得　ｃ　（　）≤４Ｌ￣－ＪＬ　Ｊ＋ｌ　（５）　然后分析在每個好畫法里．是否存在不同的子圖　和　相互交叉．　斷言１假設在畫法Ｄ內，每對　相互交叉，結合式（１）～（５），則有　Ｃｒｏ（Ｈ　）＝Ｃｒｏ（Ｋ５．　）＋Ｃｒｏ（Ｇ）＋Ｃｒｏ（Ｇ，Ｋ５，　）　≥４Ｌ￣－／Ｌ　Ｊ＋ｃｒ　（Ｇ）＋Ｃｒｏ（Ｇ，　。）．　因此，結合假設（５），有　Ｃｒｏ（Ｇ，　Ｕ　Ｔ‘）＜　．　所以能看出，在畫法Ｄ中，和Ｇ交叉的子圖　的個數不超過ｌ爭ｊ，即至少有ｌ爭Ｊ＋１個　子圖　不和Ｇ交叉．現在考慮滿足條件Ｃｒｏ（Ｇ，Ｔ　）＝０的子圖　，不失一般性，設　滿　足Ｃｒ￣（Ｇ，Ｔ　）＝０，設Ｄ　和Ｄ　分別是由畫法　Ｄ導出的Ｇ和ＧＵＴ１的子畫法．因為Ｃｒ。（Ｇ，　－）＝０．則Ｇ的畫法Ｄ　剖分整個平面，且　Ｇ的所有點都在同一個區域的邊界上：因此　白　（１）　（２）　（３）　（４）　（５）　根據文獻［１０］，找出Ｇ的所有可能的畫法Ｄ　，　見圖４．所以根據上述Ｇ的所有畫法　，有　圖４畫法　的所有可能的畫法　ＧＵ　ｔ的所有可能畫法Ｄ　．見圖５．　　，。　．　．　。　（１）　（２）　（３）　（４）　（５）　（６）　（７）　圖５　畫法Ｄ　的所有可能的畫法　現在，對所有ｉ∈｛２，３，…，ｎ｝分析這些子圖Ｇ　Ｕ　Ｔ　Ｕ　Ｔ　．對所有的ｉ∈｛２，３，…，ｎ｝，子　圖Ｇ　Ｕ　Ｔ?Ｕ　Ｔ　的每一個畫法Ｄ　把平面分成很多區域．而每個區域的邊界上要么包含Ｇ　的一部分頂點和ｔ．點，要么只包含Ｇ的一部分頂點．所以，當ｔｉ（　∈｛２，３，…，凡１）任意落　在這些區域時，且要使ｔ　和Ｇ的所有頂點相連以及滿足任意的兩個７１　和　（ｉ，ｊ∈ｆ２，３，　…，ｎ１）相互交叉，則只會出現如下兩種情況：　斷言１．１　在圖５中，除了區域　，　，　，，　和　，無論ｔｉ（　∈｛２，３，…，ｎ｝）落在　哪個區域，結合條件ＣｒＤ（Ｔ　，Ｔｊ）≥１（　，　∈｛２，３，…，ｒｑ），則Ｃｒ。（　，ＧＵＴ　）≥３；因此有　ｎ　Ｃｒｏ（ＧＵＴ　，Ｕ　Ｔ　）≥３（ｎ一１）　（６）　ｉ＝２　結合式（１）～（２），（５）和（６），有　ｌ４　汕頭大學學報（自然科學版）　第２６卷　Ｃｒｏ（Ｈ　）＝ＣｒＤ（Ｋ５　１）＋ＣｒＤ（Ｇ　Ｕ　Ｔ　）＋ＣｒＤ（Ｇ　Ｕ　Ｔｉ，Ｋ５　１）　＝ＣｒＤ（　５．　１）＋ＣｒＤ（ＧＵＴ　）＋Ｃｒｏ（ＧＵＴ　，Ｕ　Ｔ　）　≥ｚ（５，ｎ）＋３（凡一１）≥４１＿　ｊ＋ｌ孚ｊ＋３（　一１）　≥４　兒　和假設（４）矛盾．　ｊ＋　ｊ　斷言１．２在圖５的區域　：和　，內，　必須和Ｇ相交叉，又因為每兩個　和ＴＪ（ｉ，　∈｛２，３，…，ｎ｝）相互交叉，則ＣｒＤ（Ｔ　，ＧＵＴ　）≥２．　斷言ｌ－３　在圖５的區域　，ｘ　和　內，若　和Ｇ相交叉，則和斷言１．２類似，　有Ｃｒ￣（Ｔ　，ＧＵＴ　）≥２；若　不和Ｇ相交叉，則和斷言１．１類似，即Ｃｒ『ｊ（　ＧＵＴ　）≥３．　然而，對于斷言１．２和斷言１．３，假設滿足　必須和Ｇ相交叉的ｔ　的個數為　，則有　Ｃｒｏ（Ｇ　Ｕ　Ｔ　，Ｕ　Ｔ　）≥２ｘ＋３（ｎ一１一　）．　又因為由式（１）～（２），（４）～（５）和（６）以及　＜ｌ爭Ｊ，則有　Ｃｒｏ（Ｈ　）＝Ｃｒｏ（Ｋ５．　一１）＋ＣｒＤ（ＧｕＴ　）＋ＣｒＤ（Ｇｕ　，Ｋ５，　一１）　＝Ｃｒｏ（Ｋ５．　一１）＋Ｃｒｏ（ＧＵ　Ｔｉ）＋Ｃｒ￣（ＧＵ　，Ｕ　）≥Ｚ（５，ｎ）＋２　＋３（ｎ一１一　）　≥４≥Ｌ　ｌ　——　—一　ｌ半一Ｊ—　Ｊ＋２＋　＋３ｘ＋３（ｎ一１一ｎ一一　）　≥４ｌ爭兒　Ｊ＋ｌ爭Ｊ，　因此，這和假設（４）矛盾．　斷言２假設在畫法Ｄ內．至少存在兩個不同的　和　相互不交叉．不失一般性．　假設ＣｒＤ（　，Ｔ　）＝０．因為Ｈ　的子圖Ｄｕ　ｕ　７Ｔ　包含了一個子Ｋ，　而Ｃｒ（Ｋ，３）＝１；又　，因為Ｃｒ（Ｋ　）＝４，所以對所有的ｉ＝３，４，…，　，Ｃｒｏ（Ｔ　，Ｔ‘ＵＴ　）≥４，則　Ｃｒ￣（Ｈ　一２，Ｔ　Ｕ　Ｔ　）≥４（ｎ一２）＋１＝４ｎ一７．　又因為　＝　ｕ　ｔｕ　７１　，則結合上述討論，有　Ｃ　（　）＝Ｃｒｏ（Ｈ　）＋Ｃｒｏ（Ｔ　ＵＴ　）＋Ｃｒ￣（Ｈ　＿２’Ｔ　ＵＴ　）　≥４　ｌ孚兒孚Ｊ＋ｌ孚Ｊ＋４ｎ一７　≥４ｌ爭兒　Ｊ＋ｌ　，　這也和假設（４）矛盾，即定理１證畢．　定理２如果凡≥１，則有Ｃｒ（Ｇ　Ｖ　Ｐ，　）＝ｚ（５，ｎ）＋ｌ手Ｊ＋１．　證明　由圖６可知，當ｎ＝１時，結論顯然成立；然后用　數學歸納法證明當ｎ≥２時．結論也仍然成立：假設結論對ｎ一１　成立．則南圖６可知　圖６　ＧＶ　的一個好畫法　第４期　鄭敦勇等：一個五點圖和路的聯圖的交叉數　１５　Ｃｒ（ＧＶ　）≤ｚ（５，ｎ）＋ｌ—　ｊ＋１．　下證Ｃｒ（Ｇ　Ｖ　ｐ，　）≥ｚ（５，　）＋ｌ爭Ｊ＋１，又假設存在Ｇ　Ｖ　的某個最優畫法Ｄ使得　Ｃｒ。（ＧＶＰｏ）≤ｚ（５，ｎ）＋ｌ—爭ｊ＋１．　用Ｅ（Ｐｏ）表示　的邊，結合定理１，有　Ｃｒｏ（Ｇ　Ｖ　）＝Ｃｒｏ（Ｈ　Ｕ　（　））　＝Ｃｒｏ（Ｈ　）＋Ｃｒｏ（Ｅ（　））＋Ｃｒｏ（Ｈ　，Ｅ（　））　≥ｚ（５，　）＋ｌ罷一ｊ＋Ｃｒ。（ｔｔ　，Ｅ（尸，　））．　由假設（７）可知，ｃｒ。（　ＵＥ（　））＝０，　所以　中的ｎ個頂點均位于Ｇ的同一區域，又因為由圖６也可得到，　Ｃｒ（ＧＶ　）＝Ｃｒｏ（Ｋ　．　ＵＧＵＥ（　））　：Ｃｒｏ（Ｋ５．　）＋Ｃｒｏ（Ｇ　ＵＥ（　））＋Ｃｒｏ（Ｋ５　Ｇ　ＵＥ（　））　＋Ｃｒ『Ｊ（Ｋ５　，Ｇ）＋Ｃｒｏ（Ｋ５…Ｅ（　）），　≥Ｃｒｏ（Ｋ，，　）＋ＣｒＤ（Ｇ）＋Ｃｒｏ（Ｇ，Ｅ（Ｉ　ｎ））＋Ｃｒ。（　（　））　結合假設（７）可知，　Ｃｒｏ（　５，ｎ　Ｇ）＜ｌ爭ｊ，即Ｃｒｏ（　Ｔ　，Ｇ）＜ｌ手ｊ．　所以在畫法Ｄ中，和Ｇ交叉的子圖Ｔ　的個數不超過ｌ爭Ｊ，即至少有ｌ手Ｊ＋１個子圖Ｔ　不和Ｇ交叉．　’　現在考慮滿足條件Ｃｒｏ（Ｇ，Ｔｉ）＝０的子圖　不失一般性，設　’滿足Ｃｒｏ（Ｇ，Ｔ‘）＝０，　設Ｄ　和Ｄ　分別是由畫法Ｄ導出的Ｇ和Ｇ　Ｕ　Ｔ　的子畫法．因為Ｃｒｏ（Ｇ，Ｔ‘）＝０，則Ｄ的　子畫法Ｄ　剖分整個平面．且Ｇ的所有點都在同一個區域的邊界上．【大ｊ此Ｇ所有畫法如　定理１中圖４所示的一樣．而ＧＵＴ１的所有畫法與定理１中圖５所示的相同．所以．發　現定理２的證明和定理１的證明類似，證明過程如下：　情形１　因為　中的　個頂點均位于Ｇ的同一個區域，且Ｃｒ。（　Ｔ　，Ｇ）＜ｌ爭Ｊ，所　Ｉ　ｌ　以　中任何點都不可能落在圖５內不包含點ｆ。的區域里，否則將不止ｌ爭ｌ爪　和Ｇ交　叉．矛盾．　情形２在圖５中，除了不包含點ｔ。的區域，當　中ｎ個頂點落在其它任何一個區　域時，若和　中的點對應的每個７１ｌ都不和Ｇ交叉，則結合定理１的證明過程．有　Ｃ　（Ｔ　，ＧＵＴ‘）≥３，　且　Ｃｒ（ＧＶ　）：Ｃｒ。（Ｋｓ．　ＵＧＵＥ（Ｐｎ））　＝Ｃｒｏ（Ｋ５　一１）＋Ｃｒｏ（ＧＵＴ　ＵＥ（　））＋Ｃｒｏ（Ｋ５　一　，ＧＵＴ　Ｕ　（　））　１６　汕頭大學學報（自然科學版）　第２６卷　＝Ｃｒｏ（Ｋ５　１）＋ＣｒＤ（ＧＵ　Ｔ。ＵＥ（　））＋Ｃｒｏ（Ｕ　Ｔ　，Ｇ　Ｕ　Ｔ　ＵＥ（　））　ｉ＝２　≥ｚ（５，　一１）＋３（ｎ一１）　Ｉ　＾　　ｌ≥ｚ（５，ｎ一１）＋Ｌ３－．Ｊ＋１，　所以和假設（７）矛盾；而若和　中的點對應的所有　中有一部分和Ｇ交叉，且設有　個　Ｔ　和Ｇ交叉，則由前面的分析可知　必須滿足　＜ｌ手ｊ，結合定理１的證明過程，有：　當　和Ｇ交叉時，Ｃｒｏ（Ｔ　，ＧＵ　Ｔ　）≥２，否則Ｃｒｏ（Ｔ　，Ｇ　Ｕ　Ｔ　）≥３．　所以．　Ｃｒ（ＧＶ　）＝Ｃｒｏ（Ｋｓ．　ＵＧＵＥ（　））　：ＣｒＤ（Ｋ５　）＋Ｃｒｏ（Ｇ　Ｕ　Ｔ　ＵＥ（Ｐｎ））＋ＣｒＤ（Ｋ５　。，Ｇ　ｕ　Ｔ‘ＵＥ（Ｐｎ））　ＣｒＤ（Ｋ５　Ｊ）＋ＣｒＤ（ＧＵＴ　ＵＥ（　））＋ＣｒＤ（Ｕ　Ｔ　，ＧＵＴ　ＵＥ（　））　ｉ＝２　＝≥ｚ（５，ｎ一１）＋３（ｎ一１一　）＋２　ｉ，　　Ｉ≥ｚ（５，凡一１）＋Ｌ　一Ｊ＋１　這和假設（７）矛盾，因此當ｎ≥２時，定理結論也成立．　３　結語　本文研究了一個五點圖和路的聯圖的交叉數的問題．對聯圖類的交叉數的研究有一　定的參考作用．盡管目前有很多聯圖的交叉數已被確定．但大多數已有的結果都局限在　第一個因子圖階數較小的情形下．所以，我們可以不斷深化已有研究的圖類和方法，比如　可以在擴展第一個因子圖或第二個因子圖的基礎上，繼續研究聯圖的交叉數；或者去尋找　一種新的證明方法研究圖的交叉數．這都將對圖的交叉數的研究具有很大的推動作用．　參考文獻：　［１】Ｇａｒｅｙ　Ｍ　Ｒ，Ｊｏｈｎｓｏｎ　Ｄ　Ｓ．　Ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｉｓ　ＮＰ－ｃｏｍｐｌｅｔｅ［Ｊ］．ＳＩＡＭ　Ｊ　Ａｌｇｅｂｒａｉｃ　ａｎｄ　Ｄｉｓｃｒｅｔｅ　Ｍｅｔｈｏｄｓ．１９８３（４）：３１２—３１６．　［２】Ｇｒｏｈｅ　Ｍ．Ｃｏｍｐｕｔｉｎｇ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｉｎ　ｑｕａｄｒａｔｉｃ　ｔｉｍｅ［Ｊ］．Ｉｎ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３３　ｒｄ　Ａｃｍ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ　ＳＴＯ，２００１（１）：２３　１－２３６．　【３】Ｈｌｉｎｅｎｙ　Ｐｅｔｅｒ．Ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｉｓ　ｈａｒｄ　ｆｏｒ　ｃｕｂｉｃ　ｇｒａｐｈｓ，ｉｎ：Ｊｉｒｉ　Ｆｉａｌａ，Ｖａｃｌａｖ　Ｋｏｕｂｅｋ，Ｊａｎ　Ｋｒａｔｏｃｈｖｉｌ．Ｍａｔｈｅｍａｔｉｃａｌ　ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　ｃｏｍｐｕｔｅｒ　ｓｃｉｅｎｃｅ　２００４：２９　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ［Ｃ］．　Ｐｒａｇｕｅ：Ｃｚｅｃｈ　Ｒｅｐｕｂｌｉｃ，２００４（２９）：２２—２７．　【４】黃元秋，王晶．圖的交叉數綜述【Ｊ】．華東師范大學學報（自然科學版），２０１０（３）：６８—８０．　［５］Ｈａｒａｒｙ　Ｆ．Ｇｒａｐｈ　ｔｈｅｏｒｙ［Ｍ］．Ａｄｄｉｓｉｏｎ－Ｗｅｓｌｅｙ：Ｒｅａｄｉｎｇ，ＭＡ，２００４：７７２－７８２．　【６】Ｍａｒｉａｎ　Ｋｌｅｓｃ．Ｔｈｅ　ｊｉｏｎ　ｏｆ　ｇｒａｐｈ　ａｎｄ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ［Ｊ］．Ｅｌｅｃｔｒｏｎｉｃ　Ｎｏｔｅｓ　ｉｎ　Ｄｉｓｃｒｅｔｅ　Ｍａｔｈｅｍａｔｉｃｓ，　２００７（２８）：３４９－３５５．　【７］李波，王晶，黃元秋．幾個六階圖和路　的聯圖的交叉數［Ｊ］．吉首大學學報（自然科學版），２００８　（６）：２３—２８．　第４期　鄭敦勇等：一個五點圖和路的聯圖的交叉數　１７　［８】Ｂｏｎｄｙ　Ｊ　Ａ，Ｍｕｒｔｙ　Ｕ　Ｓ　Ｒ．Ｇｒａｐｈ　ｔｈｅｏｒｙ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．Ｌｏｎｄｏｎ：Ｍａｃｍｉｌｌａｎ．１９７６．　［９　Ａｒ９】ｔｕｒ　Ｋｏｒｎｉｌｏｗｉｃｚ．Ｊｏｒｄａｎ　ｃｕｒｖｅ　ｔｈｅｏｒｅｍ［Ｊ］．Ｆｏｒｍａｌｉｚｅｄ　ｍａｔｈｅｍａｔｉｃｓ，２００５（１　３）：４８　１—４９　１．　［１０】Ｓｕ　Ｚｈｅｎｇ—ｈｕａ，Ｈｕａｎｇ　Ｙｕａｎ—ｑｉｕ．Ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　ｃａｒｔｅｓｉａｎ　ｐｒｏｄｕｃｔｓ　ｏｆ　ｓｔａｒｓ　ｗｉｔｈ　ａ　５－ｖｅｒｔｅｘ　ｇｒａｐｈ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　ｍａｔｈｅｍａｔｉｃａｌ　ｒｅｓｅａｒｃｈ＆ｅｘｐｏｓｉｔｉｏｎ，２００９（４）：５８０—５８６．　［１１】Ｍａｒｉａｎ　Ｋｌｅｓｃ．Ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　Ｋ２，３ｘＣ３…．Ｄｉｓｃｒｅｔｅ　Ｍａｔｈｅｍａｔｉｃｓ，２００２．２５１：１０９—１１７．　［１　２】Ｓｚ６ｋｅｌｙ　Ｌ　Ａ．Ａ　ｓｕｃｃｅｓｓｆｕｌ　ｃｏｎｃｅｐｔ　ｆｏｒ　ｍｅａｓｕｒｉｎｇ　ｎｏｎ—ｐｌａｎａｒｉｔｙ　ｏｆ　ｇｒａｐｈ：ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ［Ｊ］．　Ｄｉｓｃｒｅｔｅ　Ｍａｔｈ，２００４，２７６：３３１—３５２．　Ｃｒｏｓｓｉｎｇ　Ｎｕｍｂｅｒ　ｏｆ　ｔｈｅ　Ｊｏｉｎ　Ｇｒａｐｈ　ｏｆ　ａ　５－Ｖｅｒｔｅｘ　Ｇｒａｐｈ　ａｎｄ　Ｐａｔｈ　ＺＨＥＮＧ　Ｄｕｎ－ｙｏｎｇ，ＨＵＡＮＧ　Ｙｕａｎ－ｑｉｕ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ，Ｈｕｎａｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ　４１００８１，Ｈｕｎａｎ，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　ｇｒａｐｈ　Ｈｎ　ｉｓ　ｓｔｕｄｉｅｄ　ａｎｄ　ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　ｔｈｅ　ｊｏｉｎ　ｇｒａｐｈ　Ｇ　Ｖ　ｏｆ　ａ　５－ｖｅｒｔｅｘ　ｇｒａｐｈ　Ｇ　ａｎｄ　ｐａｔｈ　ｉｓ　ｃｏｎｓｉｄｅｒｅｄ．Ｂｙ　ｕｓｉｎｇ　ｉｎｄｕｃｔｉｖｅ　ｐｒｉｎｃｅｐｌｅ，ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ。ｆ　ｔｈｅ　ｊｏｉｎ。ｆ　Ｇ　ａｎｄ　Ｐｎ　ｉｓ　ｓｈｏｗｎ　ａｓ　Ｃｒ（Ｇ　Ｖ　）＝４　ｌ手Ｊ　ｌ　＿ＬＪ＋ｌ爭ｊ＋１，ｆｏｒ　≥２．　Ｋｅｙ　ｗｏｒｄｓ：ｇｒａｐｈ；ｄｒａｗｉｎｇ；ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ；ｊｏｉｎ　ｇｒａｐｈ　

-