五阶图与路Pn的联图交叉数.pdf

高校应用数学学报 2014，29(2)：245—252 五阶图与路 的联图交叉数 苏振华 ，黄元秋 (1．湖南怀化学院 数学系，湖南怀化 418008 2．湖南师范大学 数学系，湖南长沙410081) 摘 要：利用KleitmanDJ给出的完全二部图的交叉数 ( ，)=z(5，n)的结果，分 别得到了联图G12V ，GIsV ，G18VPn的交叉数．同时，给出了目前已知的所有五 阶图与路的联图交叉数情况． 关键词：交叉数；联图；路；画法 中图分类号：O157．5 文献标识码：A 文章编号：1000—4424(2014)02—0245—08 §1 引 言 本文未说明的概念和术语均同文献 1【]，图G：((G)，E(G))是简单连通图．将一个图G画 在平面上时的结构，若满足如下条件： (1)任何两条相交叉的边最多交叉一次； (21边不能自身交叉； (3)有相同端点的两条边不交叉； (4)没有三条边交叉于同一点． 则称此画法为G的一个好画法．若图G的一个好画法用D表示，G中所有边与边的交叉数称 为在画法D下G的交叉数，用crD(G)表示．图G的交叉数定义为cr(G)：minD{crD(G)}，其中最 小值min取遍G的所有好画法D．若存在G的一个好画法 满2：cr~(G)=cr(G)，则称 为G的一个 最优画法． 设图G在平面上的一个好画法为D，则将由顶点，边，交叉点以及边的片断围成的部分称为 在画法D下的一个区域．两个点不相交的图G与日的联图，用GVH表示，是在G与日的并图中， 把G的每个顶点与日的每个顶点连接起来所得到的图． 图的交叉数是图的一个重要参数，研究图的交叉数不仅具有重要的理论意义，而且具有较强 的现实意义，~NVLSI中的布线问题等．然而，确定图的交叉数是一个NP一完全问题}22J．因其难度， 目前只知道一些特殊 图类的交叉数，如完全2部图 完全3部图4【】等．关于完全二部图 m的 交叉数，KleitmanDJ[3]得到了：cr( ，)=z(m，n)=lm儿 儿等儿 J，m 6，m n．其 中II表示不超过x的最大整数． 收稿 日期：2013—11-26 修回日期：2014-04．14 246 高校 应 用 数 学 学报 第29卷第2期 目前，关于联图的交叉数的研究．2007年KlescM[5]研究了 和 的联图等图类的交叉数． 2010年KlescM[6]研究了一个特殊六阶图与路R联图的交叉数．近年来，五阶图与路的联图交叉 数越来越受到学者的重视，目前五阶图与路 的联图交叉数有 7【—14】的结果． 本文在联图GtVnK】(i=12，15，18)(见表1)的交叉数的基础上，利用KleitmanDJ给出的完 全二部图的交叉数cr(K5m)=z(5，n)的结果，分别得到了联图G12V ，G15VP札，G18V 的交 叉数．同时，给出了目前已知的所有五阶图与路的联图交叉数情况． §2相关性质与引理 若 ，B是图G的两个不相交的边子集，CrD(A，B)表示AeF的边与B中的边在画法D下的交 叉数；CTD(A)表示 中的边相交叉的数 目．G1和G2是两个图，若它们都可以从同一图通过一系列 的细分得到，则称G1和G2同胚，记作G1 G2．于是，易得到下面的性质： 性质2．1 若F与G同胚，~cr(F1=cr(G)。 性质2．2 设D为图G的一个好画法．若 ，B，是图G的三个互不相交的边子集，则有 (1)crD(AUB，C)=CrD(A，C)+crD(B，c)． (2)CrD(AUB)=crD(A)+CrD(A，B)+CrD(B)． 性质2．3 (1)若日是G的子图，~cr(H) (G)； (2)设D是G的一个好画法，~cr(G) crD(c)； (3)设日l与日2均为G的子图，且日1 H2，~J]arD(H1) CrD(H2)． 性质2．4(见f1，p146])Jordan曲线定理：设 是平面上的一条Jor