笛卡尔积图K3,3×Pn的交叉数

笛卡尔积图K3,3×Pn的交叉数 笛卡尔积图K3,3×Pn的交叉数 2OO7年3月 第3o卷第1期 湖南师范大学自然科学 JournalofNaturalScienceofI-IunanNormalIJniversity V01.30No.1 Mar.,2OO7 笛卡尔积图K3.3XPn的交叉数 周智勇,黄元秋 (湖南师范大学 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 与计算机科学学院,中国长沙410081) 摘要两个图G.和G:的笛卡尔积图G.xG:是这样一个图:(G.xG2):(G.)x(G:),(G.xG2) ={(1’t,l’:)(口t,口:)Il’t=口.且l’:口:?(G2),或者l’:=口:且?.口.?(G.)}.确定了笛卡尔积图K3. ,xP.的 交叉数为7n一1. 关t词图;画法;交叉数;路;笛卡尔积 中圈分类号0157.5文献标识码A文章编号l002537(200r7)01.0031.04 TheCrossingNumberofK3, 3xP ZHOUghi-yong,HUA1VC,Yuan-qiu (Collegeofl~lathematies肌dComputerScience,I-IunanNormalIJniversity,Cha~ha410081,Chin.) Al~’aetLetG1×C2bethecartesianproductsofClwithC2,V(C1×C2)=V(C1) ×V(G2),(G1×G2)= {(1’1,l’2)(1,2)Il’1=1andl’22?(C2),OFl’2=2andl’11?(C1)}.It’sprovedthatthecrossingnumber 0f.3X尸…s7,l一1. Keywordsgraph~drawing;crossingnumber;path;cartesianproducts 本文未说明的概念和术语见文献[1],所涉及的图均指简单图.cr(C)表示图C的交叉数,指图C在平面 上的所有好画法中边与边之间的最小交叉数,其中好画法满足:(1)任何两条相交叉的边最多交叉一次;(2) 边不能自身交叉;(3)有相同端点的两条边不交叉;(4)没有3条边交叉于同一点.称含最小交叉数的好画法 为最优画法.图G在好画法D下的交叉数用cr.(C)表示.用cr(C.,C:)表示.的边与C:的边产生的交叉 收稿日期:2006-01.09 基金项目:湖南省教育厅重点资助项目(05A037) 作者简介:周智勇(1981.),男,湖南安仁人,湖南师范大学硕士研究生 32湖南师范大学自然科学第3o卷 证由于cr.(墨盛,,)?0,嗣.,和砭,,中必有(不 妨设为)墨其6个点落在子图砭.,的不同区域中.存在 由磁.,的边构成的一个图c,将(砭.,)分割为(,), 分别落在圈C的内外.又因为K,.,是3正则图,(1)若 ll=1.,有3条边与圈c交叉,则cr.(砭.3,砭.,)? 3;(2)若lI=2.宅.,至少有4条边与圈c交叉,则 cr.(墨-3’砭.,)?4;(3)若ll=3.,至少有5条边与 圈c交叉,则cr.(砭砭.,)?5.综上所述,结论成立! f| \f.I ×)×】 |/f. ,. 田.3迥3. 图1K3.,×P的一个具体的好画法D 当cr.(砭,砭.,)=3或4时的好画法容易确定,图2给出了磁砭.,自交叉 数为1时的情况. ,s,s,s . 3.3,3 (a)(b)(C) 图2砖磁.,自交叉数为1时的3种情况 用rU.,表示将的6个悬挂点连边成.,而得到的图,它与.3.,同构.用U,,U表示 在K,.,外添加两个点,Y,并与K,的点均连边得到的图,它与,,,,同构. 引理2cr(rUK3.3)=cr(K1.3.3)=3,cr(rUK3.3U)=cr(K2.3,3)=7. 引理3cr(K3.3xP1)=6. 证由上述可得:cr(.3XP)?6.下证cr(.,XP,)?6.对任意好画法D, 1.若cr.(.,)=0.收缩霹.,为点,由引理2可知.,的边至少有3个交叉,类似可知.,的边 也至少有3个交叉,因此cr.(K3.,xP)?6. 2.若cr.(.,.,)?0,则cr.(.3’.,)?3.已知K,.,交叉数在不同画法下的值是同奇偶的. (1)若cr.(.,)?3,cr.(K,,,xP)?7,大于已知上界,非最优画法. (2)若cr.(砭.,)=1(i=0,1).如果cr.(.3’,,)=3,只有1种情形.设(.,)分为(,),l l:1,ll:5(图2(a)),分别落在子图霹.,的两个不同的区域里,且任一区域的边界上至多含.,的4个 点,因此P’必然与砭.3(i=0,1)产生至少1个交叉,则crD(K3.3xP)?1+1+3+1+1=7,大于已知 上界,非最优画法.若cr.(,,)=4.,,与.,交叉的情况只有2种(如图2(b),(c)),类似可得 cr.(K3.,xP)?7,非最优画法.若cr.(.3’.,)?5.加上cr.(墨,,)(i=0,1),至少共产生7个交叉,非最 优画法.故结论成立,且在K,.,xP的任意最优画法?中,Cr(,,)=0. 引理4cr(K3.3xP2)=13 证已知cr(K3.3xP2)?13.假设存在好画法甲,使得cr(K3,3xP2)?12. 情形1若其中某个砭.,与砭.,(_『?i,J=0,1,2)都交叉.砭,,的边至产生7个交叉.当i=1时,去 掉E(.,),该子图同构于.XP,只有5个交叉,与引理3矛盾!当i=0,2时,去掉E(,,UP’),该子 图同构于K3.,xP,只有5个交叉,与引理3矛盾! 第1期周智勇等:笛卡尔积图K3.,×P的交叉数 情形2砭.,与.,(i?J,i,J=0,1,2)互不交叉.收缩l3’霹.,为点,Y,由引理3可知,.,的边至 少有7个交叉.收缩.,为点z,由引理2可知,.,与霹,,的边都至少有3个交叉,那么CI”(.,×P)?13, 与假设矛盾! 情形3, ,与霹.,其中之一交叉.不妨设CI”(,,)?0. (i)c(,,,,,):3.此情况下非最优画法,由引理3可知,至少有7个交叉.收缩.,为点Y,CI”(霹., U)?3.再考虑P与.,UPU,,的交叉情况.收缩霹.,为点,得到.,Ur.(1)若c(r) ?1,则c(,,)=1,否则. ,的边至少有7个交叉,可导出矛盾!此时,.,的区域边界上至多含有. 的 4个点,则c(P,.,)?1,又CI”(l3,r)?2,因此.,的边至少有7个交叉,可导出矛盾!(2)若 c(l3,r)=0.砖,,的6个点在一个圈上的排列情况只有3种,那么CI”(.,)?3.由于c(.3,.,)= 3,不妨设(. ,)被分割为(VI,v2),且II=5.若落在.,Ur的不同区域,c(r)?3,则 CI”(K3,,×P)?13,矛盾!若全落在子图,,Ur的某个区域里,其边界上至多含有.,的2个点,那 么c(P,.,UPU霹.,)?3.通过具体分析,无论P与或霹.3,或P交叉,都能导出c(K3.,×P) ?13,矛盾! (ii)CI”(,,,,,)?4.收缩霹.,为点,可知.,的边至少有7个交叉.去掉E(.,)后的子图同构于 . ,×P.,只有5个交叉,与引理3矛盾! 综上所述,CI”.(K3.3×P)=13. 引理5若p是K3,,×P的一个好画法(?3),且在p中每个砭,,的边至多产生6个交叉,则CI”.(., ×P)?7n一1. 证首先,,,是3一连通图,墨.,不与两个,,(z?i且i?0,)交叉.故砬和破至少有一个与 , ,不交叉,收缩其为点,由引理2知,CI”口(砭,,Ur)?3.(1)当CI”B(砖.3,砭.,)=3时,设(玛,,)分为 (VI,v2),I.I=1,II=5.V.,v2落在墨.,的两个不同的区域里.设的点为s,又i<J?,设P,为 设P,为连接,,与,,且过s点的一条n一路..霹.,与,,不交叉,与P,也不交叉,否则墨,,的边至少有7 个交叉,矛盾!若CI”.(尸|,墨.,)=o,则,,与点s落在墨.,的同一区域.,,的6个点落在墨,,的两个区域, 且有一区域的边界上至多含墨,,的4个点..,的其他点有5条路与砭.,相连,一定与墨.,的边有交叉,则 墨,,的边至少有7个交叉,矛盾!(2)当CI”(墨.3,砭,,)?4时,显然砭,,的边上至少有7个交叉,矛盾!因此, 任意-3,玛.,(i?J且i,J?0,)不交叉.r 其次,计算CI”B(K3.,×P).用q’表示由砬,.3,砬的点构成的导出子图.令f(q’)=cr口(P’,P”)+ c(P’UP”,墨,,)+cr口(.,).若在画法p下,存在两个墨,,交叉,其一定是.,或根据对称性,只考 虑cr口(.,).若cr口(.,)=0,收缩.,为点,cr口(.,Ur)?3.再收缩砬与,i=2,3, … ,一 2,得到f(q)?crp(rU墨.,U)=7,=2,3,…,一2.那么crp(,,×P)?:一,(q’)+ 6?7n一1.下面讨论crp(.3’.,)?0的情形.若crp(.3,.,)=3. 情形1当cr8(.)=1时.收缩霹.为点,cr8(r)?2,.的任一区域的边界上至多含有., 的4个点,cr.(P)?1,则.,的边至少有7个交叉,矛盾! 情形2当cr.(.,)=3时.收缩霹,,为点,得到.,Ur,其任意区域的边界上至多含有,,的2 个点,P至少有3条边产生了交叉.若这3条边中有一条边与.,交叉,.,的边至少产生7个交叉,矛盾!若 这3条边都与P交叉,cr8(P,P)?3.设H=.,UPU.,UP,令(H)表示在画法p下目的边产 生的交叉数.若c(.3)=1,则crp(.3,P)?1,(H)?11,可得,crp(K3.3×P)?7(一3)+11×2> 7n一1.若crp(.3)?3,(H)?12,可得crp(K3,3×P)?7(一3)+12×2>7n一1.若这3条边与霹,3 交叉,只能有1条边,否则霹.,的边至少产生3+4=7个交叉,矛盾!假设其他的边都与P交叉,即crB(霹l3, P)?3,cr.(P,P)?2..,不与霹.,交叉,否则.,的边产生至少7个交叉,矛盾!收缩l3,.,为点, Y.若crp(霹.,)=1,crp(霹l3,)?2(i=,Y).又crp(霹l3,P)?3,则霹,,边至少产生8个交叉,矛盾!若 crp(霹,,)=3且crp(霹l3’)=0(i=,Y),则crp(r,)?6,得到f(q)?12.当=3时,霹,,与,, 34湖南师范大学自然科学第30卷 不交叉,收缩霹.,为一点可知定,,的边产生至少3个交叉,那么crp(,,×P,)?7+l2+3>20.当/7,?4 时,(H)?9,cr日(K3,3×P)?7(/7,’一4)+12+18=7n+2>7n—I.若.(,3)?5,那么,3边产生 至少7个交叉,矛盾!. 情形3当cr日(,,)?5时.易知,,,的边产生至少8个交叉,矛盾! 若crp(l3,,,)?4.收缩眉,,为点,crp(,,Ur)?3,则.,的边至少产生7个交叉,矛盾! 综上所述,cr日(K3.3×P)?7n—I. 定理1cr(K3.3×P)=7n—I. 证用归纳法证明,当n:I,2时,由引理3,4可知结论成立!假设n=k时结论成立,当n=k+I时, 由已知上界可得,cr(.,×P)?7n—I.下证cr(K3,,×P)?7n—I.对于任意好画法D,若有某个砖,,的 边产生的交叉数大于或等于7,去掉其边,得到子图同构于K3.,×P’,可知cr.(K3.,×P川)?cr.(K3,,×P.) +7=7k—I+7=7(k+I)一I.否贝4由弓I理5可知,cr.(K3.3×P”.)?7(k+I) 一I. 综上所述,结论成立. 参考文献: [I]邦迪JA,默蒂USR.图论及其应用[M].吴望名,译.北京:科学出版 社,1984. [2]KLES:M.nIecrossingnumbersofproductsofpathsand8tarswith4-vertex 614. graphs[J].JGraphTheory,1994,18:605— [3]KLEsc.ecrossingnumberofCartesianproductsofpathswith5-vertexgraphs[J].DiscreteMath,2001,233:353—359. [4]肖文兵,黄元秋.一类笛卡尔积图的交叉数[J].湖南师范大学自然 科学,2003,4(26):3.7. [5]ASANOK.ThecrossingnumberofK1.3,andK2,3,[J].JGraphTheory,1986,10:1-8. [6]ARCHDEACOND,RICHTERRB.Ontheparityofcrossingnumbors[J].JGraphTheory,1988,12:307-310. (上接第3o页) 定理5G’表示距离圈上的顶点最长路为k的单圈图,y+.表示距离圈 上顶点的最短距离为j(j=1, 2,…,k)的所有顶点的最大度,则 (A(Gk))<max{max{+},+2}. 证用G表示圈的顶点数等于的圈的顶点数的单圈图,且对应的每一 层顶点的度数均为(.『=1, 2,…,k),可知是G的子图,所以(A(G’))?(A(G).由于(A(G))?口(GD), 所以由Frobenius定 理得’ (A(G))<max{max{~/—1+~/一.一1},?一1+2}.3《J《I 所以】(A(Gk))<max{max{~/yf一1+~/y『_l一1},~/yI—l+2}. 参考文献: BRUALDIRA.SOLHEIDES.0nthespectralradiusofconnectedgraphs[J].PI】InstMath(Bcngrad),1986,39(53):45_54. HOFMEISTERM.Spectralradiusanddegreesequence[J].MathNachr,1988,139:37-44. CONJM,TANSW.Onthespectralradiusoftrees[J].LinearAlgebraAppl,2001,329:1-8. YUA,LUM,TIANF.Onthespectralradiusofgraphs[J].LinearAlgebraAppl,2OO4,387:41-49. DASKC,KUMARP.Somenewboundsonthe8radiusofgraphs[J].DiscreteMath,2OO4,281:149-161. CVETKOVID.ROWLINSONP.Spectraofunicyclicgraphs[J].GraphsCombin,1987,3:7-23. 陈景良,陈向晖特殊矩阵[M].北京:清华大学出版社,2001. TREFETHENLN.BAUmo.Numericallinearalgebra[M].Philadelphia:SocietyforIndustrialandAppliedMathematics,1997. ROJOOSCAR.Thespectraofsometree8andboundsforthelarBteigen汕 eofanytree[J].LinearAlgebraAppl,2OO6,414:199-217 ]MINCH.Nonnegativematrices[M].NewYork:JohnWiley&SONE,1988. 列刀引m