一类笛卡尔积交叉数

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

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

确定图的交叉数是一个完全NP-问题，因为其难度，所以我们能够确定交叉数的图类很少．本文先构造F×Pn≤2n的一种好画法，由这种好画法计算出Cr（FXP。）≤4n，然后利用数学归纳法证明Cr（F×Pn）≥4n，从而确定了F与Pn的笛卡尔积交叉数即Cr（F×Pn）=4n．     

一类笛卡尔积图的交叉数

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

笛卡尔积图K2,5×Pn的交叉数

两个图G1和G2的笛卡尔积图G1×G2定义为如下的图:V(G1×G2)=V(G1)×V(G2),E(G1×G2)＝﹛(u1,u2)(v1,v2)︱u1=v1且u2v2∈E(G2),或者u2=v2且u1v1∈E(G1)﹜.确定了笛卡尔积图K(2,5)×P(n)的交叉数为8n.     

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

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

S3与Wn的笛卡尔积交叉数

本文先构造S3×Wn的一种好画法,由这种好画法计算出Cr(S3×Wn)≦2[(n-1)2/4] [n/2] 5,然后利用数学归纳法证明Cr(S3×Wn)≧2[(n-1)2/4] [n/2] 5,从而确定了S3与Wn的笛卡尔积交叉数即Cr(S3×Wn)=2[(n-1)2/4] [n/2] 5.     

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

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

G10×Sn的交叉数

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

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

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

几个六阶图与星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」.     

{P26+e}×Sn的交叉数

目前对积图交叉数的研究已经推广到6阶图与星图.计算并证明了6阶图{P²₆+e}与星S_n的积图交叉数cr({P²₆+e}×S_n)=Z(6,n)+4n.     

W4×Sn的交叉数

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

Ｃｍ＋｛ｅ１｝，Ｃｍ＋｛ｅ１｝＋｛ｅ２｝与Ｐｎ的笛卡儿积的交叉数

确定了笛卡尔积图(Ｃｍ＋｛ｅ１｝)×Ｐｎ(ｍ≥５，ｎ≥１)的交叉数，以及笛卡尔积图(Ｃｍ+｛ｅ１｝＋｛ｅ２｝)×Ｐｎ(ｍ≥５，ｎ≥１)的交叉数，其中ｅ１，ｅ２∈ｖｉｖｉ＋２（ｉ＝１，２，…，ｍ，ｉ＋２（ｍｏｄ　ｍ））.若ｅ１的端点为ｖｊ，ｖｊ＋２，则ｅ２的端点不为ｖｊ＋１.     

K5e×Sn的交叉数

K5e×Sn表示将完全图K5删除一条边e所得到的图,Sn表示星图K1,n.证明了一类特殊的图Hn的交叉数为Z(5,n)+2n以及笛卡儿积图K5e×Sn的交叉数为Z(5,n)+4n.     

W5×Sn的交叉数

轮W5的六个顶点与另外n个顶点联边得到了一类特殊的图Hn．文中先证明了Hn的交叉数为Z（6,n）＋n＋3[n/2],并在此基础上证明了轮W5与星Sn的笛卡尔积的交叉数为Z（6,n）＋2n＋3[2/2].     

笛卡尔积图的2-距离色数

图G(V,E)的2-距离染色是指正常的顶点染色,且距离不大于2的任意两个顶点着不同的颜色.给出了笛卡尔积图的一个2-距离色数的可达界,即Δ(G) Δ(H) 1≤χ2(G×H)≤2χ(G)χ2(H),以及一些特殊笛卡尔积图的2-距离色数,说明此界可达.     

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

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

几类图的笛卡尔积图的（d，1）-全标号

研究了轮Wn 与路Pm,Wn 与扇图Fm 和Wn 与Wm 的笛卡尔积的（d,1）-全标号,得出了λTd （Wn□Pm）,λTd（Wn□Fm）和λTd（Wn□Wm）的确切值。     

T（1 1/2）—型和T（2 1/2）—型邻域空间

T(1(1/2))一型和T(2(1/2))一型是两种邻域蜘,证明了它们的一些性质,推导了二者分离性之间的关系。     

K2n-1×K2n+1’的邻点可区别全染色

基于完全图的全染色和邻强边染色,得到了相邻奇数阶完全图的直积图K2n-1×K2n+1’的邻点可区别全色数χat(K2n-1×K2n+1’)=4n(n为正整数).