S_5∨C_n的交叉数

利用完全3部图K1,5,n的交叉数的结果,继续对联图Sm∨Cn（m=5）的交叉数进行研究,得到了cr（S5∨Cn）=Z（6,n）＋4「n2」＋3.     

联图K_(1,1,1,2)+P_n的交叉数

确定图的交叉数是一个NP-完全问题.目前大多数的五阶图与路的联图交叉数已经确定,但是仍有少数复杂的五阶图与路的联图交叉数没有确定.本文深化这方面的研究,在Kleitman给出的完全二部图的交叉数cr(K_(5,n))=Z(5,n)和Ho得到的完全多部图的交叉数cr(K_(1,1,1,2,n))=Z(5,n)+2n的基础上,根据图的结构特点,证明了联图K_(1,1,1,2+P_n的交叉数为Z(5,n)+2n+2.     

六阶图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.     

关于交叉数为2的联图

确定图的交叉数是NP-完全问题.Kuratowski定理刻画了平面图的结构特征,而对于交叉数为k(k≥1)的非平面图G的结构特征刻画,目前相关结果甚少.对于交叉数为1的联图G_1∨G_2,我们已经刻画出因子图G_1和G_2满足的充要条件.本文刻画了当△(G_2)≠3且cr(G_1∨G_2)=2时因子图G_1和G_2须满足的充要条件.     

关于一个特殊六阶图与路和圈的联图的交叉数

Garey和Johnson证明了确定图的交叉数问题是一个NP-难问题.目前,已确定交叉数的图类并不多.本文证明了一个特殊6阶图与n个孤立点,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+n;cr(Q+P_n)=Z(6,n)+n+1及cr(Q+C_n)=Z(6,n)+n+3.     

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$.     

一个特殊6点图Q与nK_1,P_n及C_n的联图交叉数

图的交叉数是图的一个重要参数,研究图的交叉数问题是拓扑图论中的前沿难题.确定图的交叉数是NP-难问题,因为其难度,能够确定交叉数的图类很少.通过圆盘画法途径,确定了一个特殊6点图与n个孤立点nK_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+nK_1)=Z(6,n)+2[n/2],cr(Q+P_n)=Z(6,n)+2[n/2]+1及cr(Q+C_n)=Z(6,n)+2[n/2]+3.     

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

目前已经确定的两个图的联图的交叉数结果较少.设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个顶点的路与圈.     

图Pn∨Km,n的全色数

对两个不交的图G,H,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv u∈V(G),v∈(H)},G∨H称为G和H的联图.本文得到了路Pn与完全二部图Km,n的联图Pn∨Km,n的全色数.     

W_4 ∨ C_n的交叉数

本文研究了五阶图与圈图的联图交叉数.利用假设法和比较法等方法,得到了W4∨Cn的交叉数为Z(5,n)+n+n2+4,并推广了联图交叉数的结果与方法.     

完全二分图K_(p,p)上的星博奕

本文得到完全二分图K_(p,p)上Bollobas意义下星博奕的节省成功数和成功数分别为 ec_2(K_1,n)=2n-2(n≥2),a_2(K_1,n)=2n-k,(k≥3),其中7×2~(k-3)-k≤n<7×2~(k-2)-(k+1)。     

五阶图与路P_n的联图交叉数

利用Kleitman D J给出的完全二部图的的交叉数cr(_(5,n))=Z(5,n)的结果,分别得到了联图G_(12)∨P_n,G_(15)∨P_n,G_(18)∨P_n的交叉数.同时,给出了目前已知的所有五阶图与路的联图交叉数情况.     

(Sm∪K1)+Dn的交叉数

Sm∪K1是由星图Sm与孤立点K1构成的不连通图.本文首先确定了当m=1,2,3时,(Sm∪K1)+Dn的交叉数,再在猜想cr(K6,n+1\e)=Z(6,n+1)-2{n/2」成立时,得到了(S4∪K1)+Dn的交叉数.     

联图S_5∨C_n的交叉数

两个图G和H的联图,记作G∨H,是指将G中每个点与H中的每个点连边得到的图.本文证明了星图S_5与圈C_n的联图S_5∨C_n的交叉数为Z(6,n)+4[n/2]+3(n≥3),其中Z(m,n)=[m/2][(m-1)/2][n/2][(n-1)/2],m,n为非负整数.     

完全二部图K_(1,n),K_(2,n)和K_(3,n)的点强可区别全染色

设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联或相邻的元素的颜色以及点x的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有C(u)≠C(v),则称.f是图G的一个点强可区别全染色,对一个图G进行点强可区别全染色所需的最少的颜色的数目称为G的点强可区别全色数,记为X_(vst)(G).讨论了完全二部图K_(1,n),K_(2,n)和L_(3,n)的点强可区别全色数,利用组合分析法,得到了当n≥3时,X_(vst)(K_(1,n)=n+1,当n≥4时,X_(vst)(K_(2,n)=n+2,当n≥5时,X_(vst)(K_(3,n))=n+2.     

Wm∨Pn的交叉数

在Klesc M给出的联图W_3 V P_n的交叉数的基础上,继续对联图Wm V Pn（m=4,5）的交叉数cr进行了研究,得到了cr（W3 V Pn）=Z（5,n）＋n＋「n/2＋1」以及cr（W5 V Pn）=Z（6,n）＋n＋3[n/2」＋1,n≥2.     

完全二部图K_{3,3}与星S_n的积图的交叉数

确定图的交叉数是NP-完全问题. 目前有关完全二部图与星图的积图的交叉数结果并不多. 引入了一些新的收缩技巧, 建立了积图K_{3,3}\square S_n与完全三部图K_{3,3,n}之间的交叉数关系. 从而, 为进一步完全确定积图K_{3,3}\square S_n的交叉数提供了一条新途径.     

K_(2,4)×S_n的交叉数

将K_(2,4)的6个顶点与n个点相连,得到的图记为H_n.先证明了H_n的交叉数为Z(6,n)+2n,然后证明了K_(2,4)×S_n的交叉数为Z(6,n)+4n.     

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交叉数的一个简洁方法.     

K_m∨的最小直径定向(英文)

For a graph G,let D denote an orientation of G having minimum diameter. Define f(G)=diamD.In this paper,we concentrate on exploring the minimum diameter of K_m∨(m≥1,n≥1).Some special cases are known:f(K_m∨)=∞,2,3, where m=1 and n≥1,m=2 or m≥4 and n=1,m=3 and n=1,respectively. So we only consider the case when m≥2 and n≥2.The following results are obtained. (1) f(K_m∨)=3,where m=2,3,n≥2 and m=n=4.(2) f(K_m∨)=2, where m≥5 and m is odd,2≤n≤■-m.(3) f(K_m∨)=2,where m≥4 and m≡0(mod4),2≤n≤■-(m/2 1).(4) f(K_m∨)=2,where m≥6 and m≡2(mod4),2≤n≤■-m/2.(5) f(K_m∨)=3,where m≥4,n>■.