笛卡尔积c（7,2）\{e1,e2}×Pn的交叉数

已经确定了7阶循环图c(7,2)与Pn的笛卡尔积交叉数.确定了的七个顶点的图与路、星和圈的笛卡尔积的交叉数为数不多.本文确定了c(7,2)去掉两条边后与Pn的笛卡尔积的交叉数为5n 1.     

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

在笛卡尔积图交叉数结论的基础上,研究了六阶图与星图的笛卡尔积交叉数.完全确定这类图的交叉数,其结果是:cr(G1×Sn)=6(n)/(2)(n-1)/(2) 2n,n≥1.     

一类笛卡尔积图的交叉数

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

几个六阶图与路的笛卡尔积的交叉数

计算图的交叉数问题被证明是NP-完全问题,能确定具体交叉数的图类也比较少.证明了几个六阶图与路Pn的笛卡尔积的交叉数.     

G10×Sn的交叉数

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

一类笛卡尔积交叉数

交叉数是拓朴图论研究中的一个重要课题,在笛卡尔积结论的基础上证明了一类7阶图与路的笛卡尔积图的交叉数.     

G7×Sn的交叉数

计算并证明了五阶图G7与星Sn的笛卡尔积交叉数cr(G7×Sn)=Z(5,n)+｜n/2｜,这一结果填补了Mrián Kle(s)(c)关于五阶图与星的笛卡尔积交叉数的一处空白.     

V_8与P_n的笛卡尔积的交叉数

V8是由一个圈C_8=v_1v_2v_3v_4v_5v_6v_7v_8v_1添加边v_1v_5,v_2v_6,v_3v_7,v_4v_8所得到的图,它是一个重要的3正则图.两个图的笛卡尔积的交叉数问题受到广泛的关注.运用数学归纳法证明了图V8与路Pn的笛卡尔积的交叉数是9n-1,其中n≥1.     

几个六阶图与星S_n的笛卡尔积交叉数

分别连结六阶图G1的6个顶点与其它n个顶点,得到一类特殊的图Hn.运用组合方法、归纳思想及反证法证明了Hn的交叉数为Z(6,n)+2「n/2」,并在此基础上证明G1与星K1,n的笛卡尔积的交叉数为Z(6,n)+2「n/2」;另外,证明了含子图S5的其它6个六阶图与星K1,n的笛卡尔积的交叉数都为Z(6,n)+4「n/2」.     

W4×Sn的交叉数

把轮W4的5个顶点与另外n个顶点都联边得到了一类特殊的图Hn.证明了Hn的交叉数为Z(5,n) n ﹂2n],并在此基础上证明了轮W4与星K1,n的笛卡尔积的交叉数为Z(5,n) 2n ﹂2n].     

6-阶图与路的笛卡儿积交叉数

图的交叉数是指把图画在平面上边与边产生的交叉数目的最小值。图的交叉数只在好画法中得到,好画法是指满足边自身不交叉,相关联的边不交叉,任意两条交叉的边至多交叉一次的画法。图的交叉数已被证明是一个NP-完全问题,由于其难度,要知道图的确切交叉数是非常困难的。到目前为止,只知道少数图的交叉数,其中大部分是特殊图的笛卡儿积图的交叉数,比如路,圈以及星图与点数较“少”的图的笛卡儿积交叉数。在这些基础上,应用数学归纳法,把相关结果拓展到4个6-阶图与长为的路的笛卡儿积交叉数。     

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

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

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

拓展了目前关于星与低阶图的笛卡儿积交叉数的某些结论,确定了1个特殊6-阶图与星K1,n的笛卡儿积交叉数为z(6,n)+4n,并给出了1个有在K2,4,n中加入2条边分别联结K2,4,n中2对n+2度点得到的1个特殊图类Hn的交叉数.     

K2,VCn的交叉数

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

Cayley图的笛卡尔乘积

Cayley图是由有限群导出的一类重要的高对称正则图,被认为是非常合适的互连网络拓扑结构。百笛卡尔乘积则是从小规模的指定网络构造大规模网络的重要构造方法。本文证明了Cayley图的笛卡尔乘积仍是Cayley图。作为实例,指明循环网络、超立方体、广义超立方体、超环面和立方连通圈等都是Cayley图。这样可以借助于代数方法来分析和研究这些网络的性质。     

图的交叉数综述

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