利用辅助图计算交叉数

在这篇文章中，引进了计算图交叉数的新的方法，利用辅助图计算了图C（n,m）的f-交叉数βf(n,m）），作为推论，导出了图C（n,3）和C（2m,m）的新的上界。     

图的交叉数综述

综述了图的交叉数研究诞生60余年来,国内外的研究进展和若干结果.包括了以下4个方面:一些具有特殊结构图类的交叉数;交叉数的下界;与一些参数相关的交叉数性质;以及其他类型的交叉数.     

几个循环图的交叉数(英)

运用去边和画图等方法, 确定了循环图C(m,l)(5≤m≤12,l=3)的交叉数.     

三个5-阶图与圈Cn联图的交叉数Cn

联图G∨H表示将G中每个点与H中的每个点连边得到的图．在Klesc M给出所有3阶图和4阶图与圈Cn联图的交叉数的基础上,利用反证法和排除法确定了G1,G2,G3三个5-阶图与圈Cn联图的交叉数,他们的交叉数分别是cr（G1∨C2）=Z（5,n）＋2[n/2]＋2,cr（G2∨Cn）=Z（5,n）＋2[n/2]＋2,cr（G3∨Cn）=Z（5,n）＋2[n/2]＋3.     

两个5阶图与路及圈的联图的交叉数

详细的讨论了和两个5阶图Gi(i=11,14)有关的联图的交叉数,分别是:Gi+Hn,Gi+Pn和Gi+Cn,其中Hn是由n个孤立点构成的图,Pn和Cn分别是含n个点的路和圈.     

循环图交叉数的新结果

考虑环柄对循环图交叉数的影响,并且给出了循环图交叉数的上界.特别地,循环图C(2m,m)和C(2m+l,m)的交叉数都等于1.     

广义Petersen图G(2m+1,m)的交叉数

先利用去边的方式证明了广义Petersen图G(2m+1,m)的交叉数的下界是3,然后证明它的交叉数就是3.     

C_5+e与P_n、C_n的联图交叉数

确定一个图的交叉数是NP-完全问题,能够确定的图类很少,难度很大,是国内外图论学者普遍关注的热点问题.在本文中,作者主要考虑一个特殊的五点图和路与圈的联图的交叉数,并确定了{C5+e}∨Pn及{C5+e}∨Cn的交叉数.     

循环图C(3m,m)的交叉数（英）

利用图的切割术和归纳方法, 证明了循环图 C(3m,m) 的交叉数是 m.     

几个完全二部图去掉一条边的交叉数

用km,n表示完全二部图,用Km,n\e表示完全二部图km,n去掉一条边e,先建立Km,n\e的一个好画法得到其交叉数的上界,再证明这个上界确实是K3,n\e和K4,n\e的交叉数,K3,n\e的交叉数为z(3,n)-[n/2]+1,K4,n\e的交叉数为z(4,n)-[n/2]+1.     

G10×Sn的交叉数

本文证明了五阶图G10与星Sn的笛卡尔积交叉数,填补了Marian Klesc所给出的五阶图与星图的笛卡尔积交叉数表格中的又一个空白.     

循环图C(3m,m)的交叉数

利用图的切割术和归纳方法,证明了循环图C(3m,m)的交叉数是m.     

一类笛卡尔积图的交叉数

图的交叉数是拓扑图论中的一个重要研究课题,因为其难度,能够确定交叉数的图类很少.运用同胚法和数学归纳法,确定了一类六阶图与路的笛卡尔积交叉数.     

几个六阶图与路Pn的联图的交叉数

阶数不大于5的有关的联图的交叉数已经有了一些确切结论,文中更进一步研究六阶图与路的联图的交叉数,并确定了S5∨Pn 以及其他5个六阶图 G∨Pn的交叉数.