一个五点图和路的联图的交叉数

2023年12月12日发(作者：我喜欢秋天作文)

-

２０１１年１１月　汕头大学学报（自然科学版）　第２６卷第４期　ＮＯＶ．２０１ｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｈａｎｔｏｕ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　Ｖ０Ｉ．２６　Ｎｏ．４　文章编号：１００１—４２１７（２０１１）０４　００１１—０７　一个五点图和路的联图的交叉数　郑敦勇．黄元秋　（湖南师范大学数学与计算机科学学院．湖南长沙４１００８１）　摘要：计算了一个具体图类日　的交叉数，然后研究了一个五点图Ｇ和　路的联图Ｇ　Ｖ　，　并用归纳假设法证明了这个五点图和路的联图的交叉数Ｃｒ（Ｇ　Ｖ　），即当ｎ≥２时，Ｃｒ（ＣＶ　）＝４Ｌ　儿丁Ｉ儿ｌｌ　一】　ｊ．Ｊ＋Ｌ　．　Ｊ　．ｒｔ　Ｊ＋１．Ｊ　关键词：图；画法；交叉数；联网　中图分类号：０　１５７．５　文献标识码：Ａ　Ｏ　引　言　图的交叉数是图的拓扑性质中一个重要的参数．研究图的交叉数不仅具有重要的理　论意义，也具有很大的实践意义，比如有关超大规模集成电路（ＶＬＳＩ）中的布线问题等．　然而在图论中，计算一个图的交叉数是很困难的．因为一般来说．找到一个图的交叉数　的上界所对应的画法是比较容易的．但是要证明这个画法的交叉数即最小交叉数确实非　常困难．实际上，Ｇａｒｅｙ　Ｍ　Ｒ和Ｊｏｈｎｓｏｎ　Ｄ　Ｓｔ　１证明计算一个图的交叉数的一般问题是个　ＮＰ—ｃｏｍｐｌｅｔｅ问题（读者可以分别参考文献　】中两个比较复杂的图的交叉数的结果）．目　前，我们仅仅知道几类非常有限的图的交叉数『４１，比如关于完全二部图Ｋ　的交叉数，　Ｈａｒａｒｙ　Ｆ［５】已经证明，如果ｍ≤６，则Ｃｒ（　）＝ｚ（ｍ，ｎ），这里ｚ（ｍ，ｎ）：ｌ等儿　Ｊ　ｌ争儿　ｊ；Ｍ　ｉ　ｎ　Ｋ１。　。［６１论述了联图的交叉数，并对一些特殊联图的交叉数给出了　证明；李波等人　证明了几个六阶图和路　的联图的交叉数．本文在上述基础上．研　究了一个五点图和　的联图的交叉数．　１　基本知识　本文未做说明的概念和术语均同文献［８】。且无特别说明时．所涉及的网均指连通简　收稿日期：２０１０—０６—１４　作者简介：郑敦勇（１９８６一），男，湖南常德人，硕士．研究方向：图论及其应用　Ｅ—ｍａｉｌ：ｚｈｅｎｇｄｕｎｙｏｎｇ０４１０２＠ｙａｈｏｏ．ｅｏｍ．ｃｌｌ；　黄元秋（１９６６一），男，湖南长沙人，教授．研究方向：图论及其应用　基金项目：国家自然科学基金资助项目（Ｎｏ．１０７７１０６２）　ｌ２　汕头大学学报（自然科学版）　第２６卷　单图，用Ｖ（Ｇ）和Ｅ（Ｇ）分别表示图的点集和边集．图Ｇ在曲面上的一个画法是指把图　Ｇ的顶点画为曲面上的结点．把图Ｇ的边画为曲面上的弧．两条弧的公共点称为一个交　叉．图Ｇ在曲面上的一个画法若满足下列条件：ｉ）没有任何弧自身相交；２）任何两条弧　最多相交一次：３）相邻的两条弧不相交：４）没有三条弧交于一个点．则称此画法为图Ｇ　的一个好画法．所有好画法中对应最少的交叉数目即为图Ｇ在该曲面上的交叉数．图　在平面（或球面）上的交叉数称为图Ｇ的交叉数．记为Ｃｒ（Ｇ）．令Ｄ是图Ｇ在平面上的　一个好画法，则图Ｇ在画法Ｄ中的交叉数记为　。（Ｇ）．把每个曲面上自身不相交的封闭　个区域是指　＼　的一个分支．如果两个区域的边界有一条公共弧或者公共弧的片　假设Ｇ和　是两个互不相交的图，Ｇ　Ｖ日表示Ｇ和　的联图，是通过在Ｖ（Ｇ）和　曲线称为Ｊｏｒｄａｎ曲线．且任何Ｊｏｒｄａｎ曲线把曲面一分为二［９】，所以图Ｇ在画法Ｄ中的　一段．称这两个区域是相邻的．为了方便，把图的画法中的节点也称为顶点，弧也称为边．　（　）之间添加边得到的；对于　（Ｇ）ｊ＝ｍ和　（Ｈ）『＝ｎ，ＧＶ　的边集是由Ｇ、Ｈ的边集　和完全二部图　…的边集组成的『ｏＪ．　文中计算了一个具体图类　的交叉数，并研究了五　点图Ｇ（见图１）和路　的联图Ｇ　Ｖ　，然后根据Ｈ　的画　法和Ｇ　Ｖ　的画法之间的一些关系，用数学归纳法证明了　Ｇ　Ｖ　的交叉数，即　Ｃｒ（Ｇｖ　）：４　Ｌ￣－Ｊ　Ｌ　Ｊ＋ｌ　＋１．　下面的等式很容易证明，将在下文经常使用：　Ｃｒ￣（Ａ　ＵＢ）：Ｃｒ￣（Ａ）＋Ｃｒｙ（Ｂ）＋ＣｒＤ（４，Ｂ）　Ｇ　图１　Ｇ的一个好画法　（１）　（２）　Ｃｒ￣（Ａ，ＢＵＣ）＝Ｃｒｏ（Ａ，Ｂ）＋Ｃｒ￣（Ａ，Ｃ）　其中图４，图Ｂ和图Ｃ是图中Ｅ相互不相交的子图，Ｄ是图Ｅ的一个好画法　２主要结果　　，Ｋ　的５个ｎ一　用图　表示Ｇ　ＵＫ　（Ｇ为一个五点图）．　，　度点和Ｇ的５个顶点是相同的点；对ｉ＝１，２，…，ｎ，用ｔ　表示　中ｎ个５一度点中的一个点，并且用　表示Ｋ　，　中与　ｆＩ　点ｔ　相连的５条边以及点ｔ　构成的子图，见图２，因此，有　Ｈ　：Ｇ　ｕ　５．　＝Ｇ　Ｕ（Ｕ　）　ｉ＝ｌ　（３）　图２　的一个好画法　定理１如果　≥１，Ｎ６－ｃ，（　）：ｚ（５，　）＋Ｌ争Ｊ．　证明　图３所描述的画法显示，　（Ｈ　）≤ｚ（５，ｎ）＋ｌ争ｊ＝　４　ｌ争儿旦　ｊ＋ｔｔＪ，并且如果取等号成立，则定理是对的，　所以对　进行归纳假设．当ｎ＝１和ｎ＝２时，该等式显然是　成　的，现在假设当　≥３时，　图３　Ｈ　的一个好画法　第４期　郑敦勇等：一个五点图和路的联图的交叉数　ｌ３　Ｃｒ（／Ｈ４　）≥４　）≥丁儿丁Ｊ４Ｌ　Ｊｌ孚Ｊ＋ｌ＋Ｌ　Ｊ丁Ｊ　（４）　并且假设存在一个画法Ｄ．使得　ｃ　（　）≤４Ｌ￣－ＪＬ　Ｊ＋ｌ　（５）　然后分析在每个好画法里．是否存在不同的子图　和　相互交叉．　断言１假设在画法Ｄ内，每对　相互交叉，结合式（１）～（５），则有　Ｃｒｏ（Ｈ　）＝Ｃｒｏ（Ｋ５．　）＋Ｃｒｏ（Ｇ）＋Ｃｒｏ（Ｇ，Ｋ５，　）　≥４Ｌ￣－／Ｌ　Ｊ＋ｃｒ　（Ｇ）＋Ｃｒｏ（Ｇ，　。）．　因此，结合假设（５），有　Ｃｒｏ（Ｇ，　Ｕ　Ｔ‘）＜　．　所以能看出，在画法Ｄ中，和Ｇ交叉的子图　的个数不超过ｌ争ｊ，即至少有ｌ争Ｊ＋１个　子图　不和Ｇ交叉．现在考虑满足条件Ｃｒｏ（Ｇ，Ｔ　）＝０的子图　，不失一般性，设　满　足Ｃｒ￣（Ｇ，Ｔ　）＝０，设Ｄ　和Ｄ　分别是由画法　Ｄ导出的Ｇ和ＧＵＴ１的子画法．因为Ｃｒ。（Ｇ，　－）＝０．则Ｇ的画法Ｄ　剖分整个平面，且　Ｇ的所有点都在同一个区域的边界上：因此　白　（１）　（２）　（３）　（４）　（５）　根据文献［１０］，找出Ｇ的所有可能的画法Ｄ　，　见图４．所以根据上述Ｇ的所有画法　，有　图４画法　的所有可能的画法　ＧＵ　ｔ的所有可能画法Ｄ　．见图５．　　，。　．　．　。　（１）　（２）　（３）　（４）　（５）　（６）　（７）　图５　画法Ｄ　的所有可能的画法　现在，对所有ｉ∈｛２，３，…，ｎ｝分析这些子图Ｇ　Ｕ　Ｔ　Ｕ　Ｔ　．对所有的ｉ∈｛２，３，…，ｎ｝，子　图Ｇ　Ｕ　Ｔ・Ｕ　Ｔ　的每一个画法Ｄ　把平面分成很多区域．而每个区域的边界上要么包含Ｇ　的一部分顶点和ｔ．点，要么只包含Ｇ的一部分顶点．所以，当ｔｉ（　∈｛２，３，…，凡１）任意落　在这些区域时，且要使ｔ　和Ｇ的所有顶点相连以及满足任意的两个７１　和　（ｉ，ｊ∈ｆ２，３，　…，ｎ１）相互交叉，则只会出现如下两种情况：　断言１．１　在图５中，除了区域　，　，　，，　和　，无论ｔｉ（　∈｛２，３，…，ｎ｝）落在　哪个区域，结合条件ＣｒＤ（Ｔ　，Ｔｊ）≥１（　，　∈｛２，３，…，ｒｑ），则Ｃｒ。（　，ＧＵＴ　）≥３；因此有　ｎ　Ｃｒｏ（ＧＵＴ　，Ｕ　Ｔ　）≥３（ｎ一１）　（６）　ｉ＝２　结合式（１）～（２），（５）和（６），有　ｌ４　汕头大学学报（自然科学版）　第２６卷　Ｃｒｏ（Ｈ　）＝ＣｒＤ（Ｋ５　１）＋ＣｒＤ（Ｇ　Ｕ　Ｔ　）＋ＣｒＤ（Ｇ　Ｕ　Ｔｉ，Ｋ５　１）　＝ＣｒＤ（　５．　１）＋ＣｒＤ（ＧＵＴ　）＋Ｃｒｏ（ＧＵＴ　，Ｕ　Ｔ　）　≥ｚ（５，ｎ）＋３（凡一１）≥４１＿　ｊ＋ｌ孚ｊ＋３（　一１）　≥４　儿　和假设（４）矛盾．　ｊ＋　ｊ　断言１．２在图５的区域　：和　，内，　必须和Ｇ相交叉，又因为每两个　和ＴＪ（ｉ，　∈｛２，３，…，ｎ｝）相互交叉，则ＣｒＤ（Ｔ　，ＧＵＴ　）≥２．　断言ｌ－３　在图５的区域　，ｘ　和　内，若　和Ｇ相交叉，则和断言１．２类似，　有Ｃｒ￣（Ｔ　，ＧＵＴ　）≥２；若　不和Ｇ相交叉，则和断言１．１类似，即Ｃｒ『ｊ（　ＧＵＴ　）≥３．　然而，对于断言１．２和断言１．３，假设满足　必须和Ｇ相交叉的ｔ　的个数为　，则有　Ｃｒｏ（Ｇ　Ｕ　Ｔ　，Ｕ　Ｔ　）≥２ｘ＋３（ｎ一１一　）．　又因为由式（１）～（２），（４）～（５）和（６）以及　＜ｌ争Ｊ，则有　Ｃｒｏ（Ｈ　）＝Ｃｒｏ（Ｋ５．　一１）＋ＣｒＤ（ＧｕＴ　）＋ＣｒＤ（Ｇｕ　，Ｋ５，　一１）　＝Ｃｒｏ（Ｋ５．　一１）＋Ｃｒｏ（ＧＵ　Ｔｉ）＋Ｃｒ￣（ＧＵ　，Ｕ　）≥Ｚ（５，ｎ）＋２　＋３（ｎ一１一　）　≥４≥Ｌ　ｌ　——　—一　ｌ半一Ｊ—　Ｊ＋２＋　＋３ｘ＋３（ｎ一１一ｎ一一　）　≥４ｌ争儿　Ｊ＋ｌ争Ｊ，　因此，这和假设（４）矛盾．　断言２假设在画法Ｄ内．至少存在两个不同的　和　相互不交叉．不失一般性．　假设ＣｒＤ（　，Ｔ　）＝０．因为Ｈ　的子图Ｄｕ　ｕ　７Ｔ　包含了一个子Ｋ，　而Ｃｒ（Ｋ，３）＝１；又　，因为Ｃｒ（Ｋ　）＝４，所以对所有的ｉ＝３，４，…，　，Ｃｒｏ（Ｔ　，Ｔ‘ＵＴ　）≥４，则　Ｃｒ￣（Ｈ　一２，Ｔ　Ｕ　Ｔ　）≥４（ｎ一２）＋１＝４ｎ一７．　又因为　＝　ｕ　ｔｕ　７１　，则结合上述讨论，有　Ｃ　（　）＝Ｃｒｏ（Ｈ　）＋Ｃｒｏ（Ｔ　ＵＴ　）＋Ｃｒ￣（Ｈ　＿２’Ｔ　ＵＴ　）　≥４　ｌ孚儿孚Ｊ＋ｌ孚Ｊ＋４ｎ一７　≥４ｌ争儿　Ｊ＋ｌ　，　这也和假设（４）矛盾，即定理１证毕．　定理２如果凡≥１，则有Ｃｒ（Ｇ　Ｖ　Ｐ，　）＝ｚ（５，ｎ）＋ｌ手Ｊ＋１．　证明　由图６可知，当ｎ＝１时，结论显然成立；然后用　数学归纳法证明当ｎ≥２时．结论也仍然成立：假设结论对ｎ一１　成立．则南图６可知　图６　ＧＶ　的一个好画法　第４期　郑敦勇等：一个五点图和路的联图的交叉数　１５　Ｃｒ（ＧＶ　）≤ｚ（５，ｎ）＋ｌ—　ｊ＋１．　下证Ｃｒ（Ｇ　Ｖ　ｐ，　）≥ｚ（５，　）＋ｌ争Ｊ＋１，又假设存在Ｇ　Ｖ　的某个最优画法Ｄ使得　Ｃｒ。（ＧＶＰｏ）≤ｚ（５，ｎ）＋ｌ—争ｊ＋１．　用Ｅ（Ｐｏ）表示　的边，结合定理１，有　Ｃｒｏ（Ｇ　Ｖ　）＝Ｃｒｏ（Ｈ　Ｕ　（　））　＝Ｃｒｏ（Ｈ　）＋Ｃｒｏ（Ｅ（　））＋Ｃｒｏ（Ｈ　，Ｅ（　））　≥ｚ（５，　）＋ｌ罢一ｊ＋Ｃｒ。（ｔｔ　，Ｅ（尸，　））．　由假设（７）可知，ｃｒ。（　ＵＥ（　））＝０，　所以　中的ｎ个顶点均位于Ｇ的同一区域，又因为由图６也可得到，　Ｃｒ（ＧＶ　）＝Ｃｒｏ（Ｋ　．　ＵＧＵＥ（　））　：Ｃｒｏ（Ｋ５．　）＋Ｃｒｏ（Ｇ　ＵＥ（　））＋Ｃｒｏ（Ｋ５　Ｇ　ＵＥ（　））　＋Ｃｒ『Ｊ（Ｋ５　，Ｇ）＋Ｃｒｏ（Ｋ５…Ｅ（　）），　≥Ｃｒｏ（Ｋ，，　）＋ＣｒＤ（Ｇ）＋Ｃｒｏ（Ｇ，Ｅ（Ｉ　ｎ））＋Ｃｒ。（　（　））　结合假设（７）可知，　Ｃｒｏ（　５，ｎ　Ｇ）＜ｌ争ｊ，即Ｃｒｏ（　Ｔ　，Ｇ）＜ｌ手ｊ．　所以在画法Ｄ中，和Ｇ交叉的子图Ｔ　的个数不超过ｌ争Ｊ，即至少有ｌ手Ｊ＋１个子图Ｔ　不和Ｇ交叉．　’　现在考虑满足条件Ｃｒｏ（Ｇ，Ｔｉ）＝０的子图　不失一般性，设　’满足Ｃｒｏ（Ｇ，Ｔ‘）＝０，　设Ｄ　和Ｄ　分别是由画法Ｄ导出的Ｇ和Ｇ　Ｕ　Ｔ　的子画法．因为Ｃｒｏ（Ｇ，Ｔ‘）＝０，则Ｄ的　子画法Ｄ　剖分整个平面．且Ｇ的所有点都在同一个区域的边界上．【大ｊ此Ｇ所有画法如　定理１中图４所示的一样．而ＧＵＴ１的所有画法与定理１中图５所示的相同．所以．发　现定理２的证明和定理１的证明类似，证明过程如下：　情形１　因为　中的　个顶点均位于Ｇ的同一个区域，且Ｃｒ。（　Ｔ　，Ｇ）＜ｌ争Ｊ，所　Ｉ　ｌ　以　中任何点都不可能落在图５内不包含点ｆ。的区域里，否则将不止ｌ争ｌ爪　和Ｇ交　叉．矛盾．　情形２在图５中，除了不包含点ｔ。的区域，当　中ｎ个顶点落在其它任何一个区　域时，若和　中的点对应的每个７１ｌ都不和Ｇ交叉，则结合定理１的证明过程．有　Ｃ　（Ｔ　，ＧＵＴ‘）≥３，　且　Ｃｒ（ＧＶ　）：Ｃｒ。（Ｋｓ．　ＵＧＵＥ（Ｐｎ））　＝Ｃｒｏ（Ｋ５　一１）＋Ｃｒｏ（ＧＵＴ　ＵＥ（　））＋Ｃｒｏ（Ｋ５　一　，ＧＵＴ　Ｕ　（　））　１６　汕头大学学报（自然科学版）　第２６卷　＝Ｃｒｏ（Ｋ５　１）＋ＣｒＤ（ＧＵ　Ｔ。ＵＥ（　））＋Ｃｒｏ（Ｕ　Ｔ　，Ｇ　Ｕ　Ｔ　ＵＥ（　））　ｉ＝２　≥ｚ（５，　一１）＋３（ｎ一１）　Ｉ　＾　　ｌ≥ｚ（５，ｎ一１）＋Ｌ３－．Ｊ＋１，　所以和假设（７）矛盾；而若和　中的点对应的所有　中有一部分和Ｇ交叉，且设有　个　Ｔ　和Ｇ交叉，则由前面的分析可知　必须满足　＜ｌ手ｊ，结合定理１的证明过程，有：　当　和Ｇ交叉时，Ｃｒｏ（Ｔ　，ＧＵ　Ｔ　）≥２，否则Ｃｒｏ（Ｔ　，Ｇ　Ｕ　Ｔ　）≥３．　所以．　Ｃｒ（ＧＶ　）＝Ｃｒｏ（Ｋｓ．　ＵＧＵＥ（　））　：ＣｒＤ（Ｋ５　）＋Ｃｒｏ（Ｇ　Ｕ　Ｔ　ＵＥ（Ｐｎ））＋ＣｒＤ（Ｋ５　。，Ｇ　ｕ　Ｔ‘ＵＥ（Ｐｎ））　ＣｒＤ（Ｋ５　Ｊ）＋ＣｒＤ（ＧＵＴ　ＵＥ（　））＋ＣｒＤ（Ｕ　Ｔ　，ＧＵＴ　ＵＥ（　））　ｉ＝２　＝≥ｚ（５，ｎ一１）＋３（ｎ一１一　）＋２　ｉ，　　Ｉ≥ｚ（５，凡一１）＋Ｌ　一Ｊ＋１　这和假设（７）矛盾，因此当ｎ≥２时，定理结论也成立．　３　结语　本文研究了一个五点图和路的联图的交叉数的问题．对联图类的交叉数的研究有一　定的参考作用．尽管目前有很多联图的交叉数已被确定．但大多数已有的结果都局限在　第一个因子图阶数较小的情形下．所以，我们可以不断深化已有研究的图类和方法，比如　可以在扩展第一个因子图或第二个因子图的基础上，继续研究联图的交叉数；或者去寻找　一种新的证明方法研究图的交叉数．这都将对图的交叉数的研究具有很大的推动作用．　参考文献：　［１】Ｇａｒｅｙ　Ｍ　Ｒ，Ｊｏｈｎｓｏｎ　Ｄ　Ｓ．　Ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｉｓ　ＮＰ－ｃｏｍｐｌｅｔｅ［Ｊ］．ＳＩＡＭ　Ｊ　Ａｌｇｅｂｒａｉｃ　ａｎｄ　Ｄｉｓｃｒｅｔｅ　Ｍｅｔｈｏｄｓ．１９８３（４）：３１２—３１６．　［２】Ｇｒｏｈｅ　Ｍ．Ｃｏｍｐｕｔｉｎｇ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｉｎ　ｑｕａｄｒａｔｉｃ　ｔｉｍｅ［Ｊ］．Ｉｎ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３３　ｒｄ　Ａｃｍ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ　ＳＴＯ，２００１（１）：２３　１－２３６．　【３】Ｈｌｉｎｅｎｙ　Ｐｅｔｅｒ．Ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｉｓ　ｈａｒｄ　ｆｏｒ　ｃｕｂｉｃ　ｇｒａｐｈｓ，ｉｎ：Ｊｉｒｉ　Ｆｉａｌａ，Ｖａｃｌａｖ　Ｋｏｕｂｅｋ，Ｊａｎ　Ｋｒａｔｏｃｈｖｉｌ．Ｍａｔｈｅｍａｔｉｃａｌ　ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　ｃｏｍｐｕｔｅｒ　ｓｃｉｅｎｃｅ　２００４：２９　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ［Ｃ］．　Ｐｒａｇｕｅ：Ｃｚｅｃｈ　Ｒｅｐｕｂｌｉｃ，２００４（２９）：２２—２７．　【４】黄元秋，王晶．图的交叉数综述【Ｊ】．华东师范大学学报（自然科学版），２０１０（３）：６８—８０．　［５］Ｈａｒａｒｙ　Ｆ．Ｇｒａｐｈ　ｔｈｅｏｒｙ［Ｍ］．Ａｄｄｉｓｉｏｎ－Ｗｅｓｌｅｙ：Ｒｅａｄｉｎｇ，ＭＡ，２００４：７７２－７８２．　【６】Ｍａｒｉａｎ　Ｋｌｅｓｃ．Ｔｈｅ　ｊｉｏｎ　ｏｆ　ｇｒａｐｈ　ａｎｄ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ［Ｊ］．Ｅｌｅｃｔｒｏｎｉｃ　Ｎｏｔｅｓ　ｉｎ　Ｄｉｓｃｒｅｔｅ　Ｍａｔｈｅｍａｔｉｃｓ，　２００７（２８）：３４９－３５５．　【７］李波，王晶，黄元秋．几个六阶图和路　的联图的交叉数［Ｊ］．吉首大学学报（自然科学版），２００８　（６）：２３—２８．　第４期　郑敦勇等：一个五点图和路的联图的交叉数　１７　［８】Ｂｏｎｄｙ　Ｊ　Ａ，Ｍｕｒｔｙ　Ｕ　Ｓ　Ｒ．Ｇｒａｐｈ　ｔｈｅｏｒｙ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］．Ｌｏｎｄｏｎ：Ｍａｃｍｉｌｌａｎ．１９７６．　［９　Ａｒ９】ｔｕｒ　Ｋｏｒｎｉｌｏｗｉｃｚ．Ｊｏｒｄａｎ　ｃｕｒｖｅ　ｔｈｅｏｒｅｍ［Ｊ］．Ｆｏｒｍａｌｉｚｅｄ　ｍａｔｈｅｍａｔｉｃｓ，２００５（１　３）：４８　１—４９　１．　［１０】Ｓｕ　Ｚｈｅｎｇ—ｈｕａ，Ｈｕａｎｇ　Ｙｕａｎ—ｑｉｕ．Ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　ｃａｒｔｅｓｉａｎ　ｐｒｏｄｕｃｔｓ　ｏｆ　ｓｔａｒｓ　ｗｉｔｈ　ａ　５－ｖｅｒｔｅｘ　ｇｒａｐｈ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　ｍａｔｈｅｍａｔｉｃａｌ　ｒｅｓｅａｒｃｈ＆ｅｘｐｏｓｉｔｉｏｎ，２００９（４）：５８０—５８６．　［１１】Ｍａｒｉａｎ　Ｋｌｅｓｃ．Ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　Ｋ２，３ｘＣ３…．Ｄｉｓｃｒｅｔｅ　Ｍａｔｈｅｍａｔｉｃｓ，２００２．２５１：１０９—１１７．　［１　２】Ｓｚ６ｋｅｌｙ　Ｌ　Ａ．Ａ　ｓｕｃｃｅｓｓｆｕｌ　ｃｏｎｃｅｐｔ　ｆｏｒ　ｍｅａｓｕｒｉｎｇ　ｎｏｎ—ｐｌａｎａｒｉｔｙ　ｏｆ　ｇｒａｐｈ：ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ［Ｊ］．　Ｄｉｓｃｒｅｔｅ　Ｍａｔｈ，２００４，２７６：３３１—３５２．　Ｃｒｏｓｓｉｎｇ　Ｎｕｍｂｅｒ　ｏｆ　ｔｈｅ　Ｊｏｉｎ　Ｇｒａｐｈ　ｏｆ　ａ　５－Ｖｅｒｔｅｘ　Ｇｒａｐｈ　ａｎｄ　Ｐａｔｈ　ＺＨＥＮＧ　Ｄｕｎ－ｙｏｎｇ，ＨＵＡＮＧ　Ｙｕａｎ－ｑｉｕ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ，Ｈｕｎａｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ　４１００８１，Ｈｕｎａｎ，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　ｇｒａｐｈ　Ｈｎ　ｉｓ　ｓｔｕｄｉｅｄ　ａｎｄ　ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ　ｏｆ　ｔｈｅ　ｊｏｉｎ　ｇｒａｐｈ　Ｇ　Ｖ　ｏｆ　ａ　５－ｖｅｒｔｅｘ　ｇｒａｐｈ　Ｇ　ａｎｄ　ｐａｔｈ　ｉｓ　ｃｏｎｓｉｄｅｒｅｄ．Ｂｙ　ｕｓｉｎｇ　ｉｎｄｕｃｔｉｖｅ　ｐｒｉｎｃｅｐｌｅ，ｔｈｅ　ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ。ｆ　ｔｈｅ　ｊｏｉｎ。ｆ　Ｇ　ａｎｄ　Ｐｎ　ｉｓ　ｓｈｏｗｎ　ａｓ　Ｃｒ（Ｇ　Ｖ　）＝４　ｌ手Ｊ　ｌ　＿ＬＪ＋ｌ争ｊ＋１，ｆｏｒ　≥２．　Ｋｅｙ　ｗｏｒｄｓ：ｇｒａｐｈ；ｄｒａｗｉｎｇ；ｃｒｏｓｓｉｎｇ　ｎｕｍｂｅｒ；ｊｏｉｎ　ｇｒａｐｈ　

-