S4 V Cn的交叉数

将星图S4的每个顶点与Cn每个点相连,得到的图记为S1VCn.本文证明了S1VCn的交叉数为Z(5,n)+2|n/2|+2.     

图的交叉数综述

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

一个五阶图与星图的笛卡尔积交叉数

确定图的交叉数被证明是一个NP-完全问题,因为其难度,能够确定交叉数的具体图类非常少.M.Klecˇ等人确定了一些关于阶数不超过5的图与路、星和圈的笛卡尔积图的交叉数.本文扩展了他们的结果,确定了1个5阶图与星图的笛卡尔积图的交叉数.     

一个六阶图与星图的笛卡儿积的交叉数

图的交叉数已被证明是一个NP-完全问题, 由于其难度, 要知道图的确切交叉数是非常困难的. 到目前为止,只知道少数图的交叉数, 其中大部分是特殊图的笛卡儿积图的交叉数, 比如路, 圈以及星图与点数较"少"的图的笛卡儿积交叉数. 在这些基础上, 应用数学归纳法, 把相关结果拓展到1个6-阶图G,并确定它与星的笛卡儿积交叉G×Sn Z(6,n) 3[n/2] .     

K2,VCn的交叉数

将完全二部图K2,3的每个顶点与Cn每个点相连,得到的图记为K2,3 VCn.利用一些完全多部图的交叉数结论,将K23VCn与K2,3,n比较,证明了K23VCn的交叉数为Z(5,n)+n+3.     

K_(2,3)∨C_n的交叉数

将完全二部图K_(2,3)的每个顶点与C_n每个点相连,得到的图记为K_(2,3)∨C_n.利用一些完全多部图的交叉数结论,将K_(2,3)∨C_n与K_(2,3,n)比较,证明了K_(2,3)∨C_n的交叉数为Z(5,n)+n+3.     

星图S5及5个六阶图与路的笛卡儿积图的交叉数

两个图G1和G2的笛卡尔积图G1×G2是这样一个图:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,u2)(v1,v2)|u1=v1,且u2、v2∈E(G2)或者u2=v2,且u1、v1∈E(G1)}.星图Sm表示完全偶图K1,m,Pn表示长为n的路.这里确定了星图S5及5个六阶图与路的笛卡儿积图的交叉数.     

完全4-部图的交叉数

用分情况讨论法证明了完全4-部图K_(1,1,1,n)、K_(1,1,2,n)、K_(1,1,3,n)的交叉数分别为Z(3,n)、Z(4,n) (N/2)、Z(5,n) n (N/2)(n≥1).     

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

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

Fubini定理公式数计数和(φ)(n,k)卷积公式

组合数学中,Catalan数有显式公式,Fibini定理公式数无显式公式,本文利用完全图Kn的k个分支的完全分支覆盖的个数N(Knk)=S(n,k)(第二类Stirling数)和卷积公式,作者将导出Fibini定理的公式数的显式公式,此外获得完全i-部图所有个数计数公式,本文中提出φ(n,k)概念,并讨论φ(n,k)的组合卷积公式,最后证明φ(n)=sumfork=1ton(1/k)φ(n,k)与Fibini公式数之间的关系等式。     

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

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

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

计算了一个具体图类Hn的交叉数,然后研究了一个五点图G和Pn路的联图G∨Pn,并用归纳假设法证明了这个五点图和路的联图的交叉数Cr(G∨Pn),即当n≥2时,Cr(G∨Pn)=4 2n n 2-1+n2+1.     

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

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

完全二部图k_(4,n)去掉两条边的交叉数

用km,n表示完全二部图,用k4,ne1,e2表示完全二部图k4,n去掉两条边e1、e2。本文确定了K4,ne1,e2的交叉数为z(4,n)-22n+2。K4,ne1,e2。     

三个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.     

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

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