7阶循环图C（7，2）Pn的笛卡儿积的交叉数

C（7，2）表示由圈C7（v1v2…v7v1）增加边vivi＋2（i=1，2，…，7，i＋2（mod7））所得的循环图．目前没有有关七阶图与路、星和圈的笛卡尔积交叉数的结果，我们证明了7阶循环图C（7，2）与路R的笛卡儿积的交叉数是8n．     

循环图C(9,2)与路Pn的笛卡儿积的交叉数

C(m,2)表示由圈Cm(v1v2…vmv1)增加边vivi+2(i=1,…,m,i+2 (mod m))所得的循环图.C(m,2)的一点悬挂(两点悬挂)是增加一个顶点x(两个顶点x,y)和边xv(边xv,yv)的图,其中v∈V(C(m,2)).我们证明了9阶循环图C(9,2)与路Rn的笛卡儿积的交叉数是10n;C(2m-1,2)的一点悬挂和两点悬挂的交叉数分别是m,2m.     

循环图C(12,2)与路P_n的笛卡尔积的交叉数

循环图C(m,2)表示由圈Cm(v_1v_2…v_mv_1)增加边v_iv_i+2(i=1,2,…,m,i+2(modm))所得到的图,本文证明了循环图C(12,2)与路P_n的笛卡尔积的交叉数是12n.     

一个六阶3-连通图与路Pn的笛卡尔积的交叉数

C(6,2)表示由圈C6增加边vivi 2(i=1,…,6,i 2(m od6))所得的图,把边vivi 2叫做C(6,2)的弦,B表示C(6,2)除去一条弦所得到的图,我们确定了B与Pn笛卡尔积的交叉数为5n-1.     

循环图C(10,2)与路P_n的笛卡尔积的交叉数

证明了循环图C(10,2)与路P_n的笛卡尔积的交叉数是10n及循环图C(2m,2)的一点悬挂和两点悬挂的交叉数分别是m,2m.     

笛卡尔积K_(1,1,2,2)×P_n的交叉数

已经确定了的六个顶点的图与路、星和圈的笛卡尔积的交叉数为数不多,作者们继续深化这方面的研究,确定了K1,1,2,2与路Pn的笛卡尔积的交叉数为9n-1.     

泊松图P(4,1)与路Pn的笛卡尔积的交叉数

泊松图$P(m, 1)$与路$P_n$的笛卡尔积的交叉数是一个NP-完全问题, Y.H. Peng和Y.C.Yiew 证明了$P(3,1)$与$P_n$的笛卡尔积的交叉数为$4n$, 我们证明明了$P(4,1)$与$P_n$的笛卡尔积的交叉数为$8n$.     

W5×Sn的交叉数

确定图的交叉数是-个NP一完全问题.目前,对于六阶图与星图笛卡尔积的交叉数知之甚少.收稿证明了W5 X.Sn的交叉数为6[n/2][n-1/2] 2n 3[n/2]([x]表示不超过x的最大整数),并得到了W5的部分子图与Sn笛卡尔积的交叉数.     

六阶图G与Sn的积图的交叉数

确定图的交叉数是NP．完全问题．目前已确定交叉数的六阶图与星图的笛卡尔积图极少。本文确定了—个六阶图G与星图5k积图的交叉数为Z（6,n）＋2n＋[n/2].     

交叉数为2的笛卡尔积图

图G的交叉数,记作cr(G),是把G画在平面上的所有画法中边与边产生交叉的最小数目,它是拓扑图论中的一个热点问题。Kle?c和Petrillová刻画了当G₁为圈且cr(G₁G₂)-2时,因子图G₁和G₂满足的充要条件。在此基础上,本文研究当|V(G₁)|≥3且cr(G₁G₂)=2时,G₁和G₂应满足的充要条件。     

$K_{5}\times S_{n}$ 的交叉数

把完全图$K_{5}$的五个顶点与另外$n$个顶点都联边得到一类特殊的图$H_{n}$.文中证明了$H_{n}$的交叉数为$Z(5,n)+2n+\lfloor \frac{n}{2}\rfloor+1$,并在此基础上证明了$K_{5}$与星$K_{1,n}$的笛卡尔积的交叉数为$Z(5,n)+5n+\lfloor\frac{n}{2} \rfloor+1$.     

K_(1,1,m)□P_n的交叉数

借助拉链积运算,Cartesian积图K(1,m)□Pn和K(2,m)□Pn的交叉数最近被先后确定.本文进一步证明了:对于m,n≧1,有cr(K(1,1,m)□Pn)=2n[m/2][(m-1)/2]+(n-1)[m/2].结论的证明基于Bokal关于树的Cartesian积图交叉数的有关结果.另外,我们也给出了确定K(2,m)□Pn交叉数的一个简洁方法.     

三类笛卡尔积图的关联色数

图的关联色数的概念是 Brualdi和 Massey于 1 993年引入的 ,它同图的强色指数有密切的关系 .Guiduli[2 ] 说明关联色数是有向星萌度的一个特殊情况 ,迄今仅确定了某些特殊图类的关联色数 .本文给出了完全图与完全图、圈与完全图、圈与圈的笛卡尔积图的关联色数。     

K2,4×Sn的交叉数

Garey和Johnson证明了确定图的交叉数是一个NP-完全问题.确定了笛卡尔积图$K_{2,4}\times S_{n}$的交叉数是$Z(6,n)+4n.$ 当$m\geq 5,$猜想${\rm cr}(K_{2,m}\timesS_{n})={\rm cr}(K_{2,m,n})+n\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor$.     

六阶图Q与星图S_n的积图交叉数

目前关于积图的交叉数的研究已经推广到六阶图与星图的积图.研究得到了一个特殊六阶图Q与n个孤立点nK_1的联图交叉数,然后通过收缩的方法,得到了Q与星图S_n的积图交叉数.     

W6*Sn的交叉数

早在20世纪50年代,Zarankiewicz 猜想完全2-部图K_{m,n}(m\leq n)的交叉数为\lfloor\frac{m}{2}\rfloor\times \lfloor\frac{m-1}{2}\rfloor\times\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor (对任意实数x,\lfloor x\rfloor表示不超过x的最大整数). 目前这一猜想的正确性只证明了当m\leq6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立,确定了6-轮W_{6}与星S_{n}的笛卡尔积图的交叉是 cr(W_{6}\times S_{n})=9\lfloor\frac{n}{2}\rfloor\times\lfloor\frac{n-1}{2}\rfloor+2n+5\lfloor\frac{n}{2}\rfloor.     

一个五阶图与路、圈的联图的交叉数

目前已经确定的两个图的联图的交叉数结果较少.设H是由一个4圈及一个孤立点所构成的5阶图.研究了图H与路、圈的联图的交叉数,得到了cr(H+P_n)=Z(5,n)+[n/2]+l,cr(H+C_n):Z(5,n)+[n/2]+2,其中,P_n与C_n分别表示含n个顶点的路与圈.     

K2,4× Pn 的交叉数

该文确定了完全二部图 $K_{2,4}$ 与路 $P_n$ 的笛卡儿积图的交叉数.     

K_m~-□P_n的交叉数

Klesc等人先后确定了K_m~-□P_n(4≤m≤6)的交叉数,本文利用构造法确定了K_m-2K_2(4≤m≤12,m≠10,12)的交叉数.在此基础上,可进一步确定K_m~-□P_n(4≤m≤9,m≠8)的交叉数.相比而言,我们所采用的方法更具一般性.     

六阶图C_6+3K_2与P_n,C_n的联图交叉数

用P_n表示n个点的路,C_n表示长为n的圈,C_6+3K_2表示圈C_6添加三条相邻的边3K_2=C_3得到的图.在Kleitman给出的完全二部图的交叉数cr(K_(6,n))=Z(6,n)的基础上,得到了特殊六阶图C_6+3K_2与路P_n,圈C_n的联图交叉数分别为Z(6,n)+3[n/2]+2与Z(6,n)+3[n/2]+4.