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

分别讨论了5阶图G16与nK1,Pn,Cn联图的交叉数,得到cr(G16+nK1)=Z(5,n)+n+n/2,n≥1;cr(G16+Pn)=Z(5,n)+n+n/2+1,n≥2;cr(G16+Cn)=Z(5,n)+n+n/2+3,n≥3,其中nK1是n个孤立点构成的图,Pn,Cn分别是含n个点的路和圈.     

六阶图H与路P_n,圈C_n的联图交叉数

目前已确定交叉数的六阶图与路,圈的联图较少.在Kleitman给出的完全二部图的交叉数cr(K6,n)=Z(6,n)的结果的基础上,通过分析法得到了一个特殊六阶图H与路Pn,与圈Cn的联图交叉数分别为Z(6,n)+n+■n/2」+1和Z(6,n)+n+■n/2」+3.     

一类字典积Cn[H]的星全染色

简单图G和H的字典积G[H]是指具有顶点集V(G)×V(H)的简单图G[H],其顶点(u,v)和另一个顶点(u’,v’)相邻当且仅当uu’∈E(G),或者u=u’且vv’∈E(H).研究了n阶圈Cn与m阶简单图H的字典积Cn[H]的星全染色,得到了圈与某些特殊图的字典积的星全色数.     

一类联图的交叉数

图的交叉数是表征一个图的非平面性的一个重要的参数。本文运用圆盘画法这一途径,确定了一个特殊6阶图与n个孤立点,n K_1,路P_n及圈C_n的联图的交叉数分别是cr(Q+n K_1)=Z(6,n)+■2n/2」;cr(Q+P_n)=Z(6,n)+■2n/2」+1;cr(Q+Q_n)=Z(6,n)+■2n/2」+3。     

联图Cn∨Kn的邻强边色数

研究了联图Cn∨Kn的邻强边染色,证明了当n=3时,χ′as(Cn∨Kn)=7;当n4时,χ′as(Cn∨Kn)=2n.     

W5×Sn的交叉数

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

W5×Sn的交叉数

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

k连通［s,t］图的Hamiltion连通性

若图G的任意个s顶点的导出子图至少有t条边,则称图G为[s,t]图．[s,t]图的概念可视为图的独立数概念的推广．本文证明：若图G是k连通[k＋1,2]（k≥2）图,则G或者是Hamilton连通的或者同构于Kk∨Gk．由此可以推出,若图G的阶是n（n≥3）,α（G）≤κ（G）－1,则G是Hamilton连通的．     

图中含有给定圈的正则因子存在性度条件

设n和r是正整数使得r≥n＋1≥4．一个图被称为K1,n-free图，如果它不含导出子图K1,n。证明了：若G是一个有圈H的图且r｜V（G）｜为偶数，G—E（H）是连通的K1,n-free图且G—E（H）的顶点最小度至少是（n（r＋1）-3/r-2）[rn-2/2（n-1）]-n-1/r-2（[rn-2/2（n-1）]）^2＋n-3那么G有r-因子F包含H中的所有的边．     

两个5阶图与路及圈的联图的交叉数

详细的讨论了和两个5阶图Gi(i=11,14)有关的联图的交叉数,分别是:Gi+Hn,Gi+Pn和Gi+Cn,其中Hn是由n个孤立点构成的图,Pn和Cn分别是含n个点的路和圈.     

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

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

两类非连通图优美性的研究

给出了两类非连通图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)和(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1(k=1,2), 并证明了如下结论:对自然数n, m, m1, m2, m3, 设s=〖JB(［〗〖SX(〗n〖〗2〖SX)〗〖JB)］〗, n≥9, m1≥s+2, 则图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)是一个优美图; 对 k=1,2,设n, m≥3, G(k)n-1是一个具有n-1条边的k-优美图,则图(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1是一个优美图。 其中,K2是一个具有2个顶点的完全图,K2〖TX-〗是图K2的补图,K2〖TX-〗∨Cn是图K2和n圈Cn的联图, St(m)是一个具有m+1个顶点的星形树。     

联图P_3∨K_(m,n)和C_4∨K_(m,n)的邻强边色数

设计一个具有分支限界技术的算法来研究联图P3∨Km,n和C4∨Km,n的k-邻强边染色,并证明mn-3时它们的邻强边色数均为m+n+3.     

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

Cartesian积图的最大拉普拉斯特征值

设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))～(1/2))]+((2p-1)～(1/2))+1.     

K2,VCn的交叉数

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

几个六阶图与路Pn的联图的交叉数

阶数不大于5的有关的联图的交叉数已经有了一些确切结论,文中更进一步研究六阶图与路的联图的交叉数,并确定了S5∨Pn 以及其他5个六阶图 G∨Pn的交叉数.     

关于路核和路剖分的新研究

图G的最长路的阶称为环游阶,记为τ（G）。顶点集V（G）的子集S称为图G的Pn-核,如果满足τ（G[S]）≤n-1且V（G）-S的每一个顶点v都与G[S]中阶为n-1路的端顶点相连。把顶点集V（G）剖分成A,B两部分,使得τ（G[A]）≤a和τ（G[B]）≤b,此剖分称为图G的一个（a,b）-剖分。本文证明了对于n≤3g/2-1的正整数,任意围长为g的图都有一个Pn＋1-核。并且还得到,如果τ（G）=a＋b,其中1≤a≤b,图G的围长g≥2/3（a＋1）,那么G有一个（a,b）-剖分。     

几类图的均匀邻点可区别全染色

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G（V,E）为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|－|Vj∪Ej||≤1（i≠j）,其中,Vi∪Ei={v|f（v）=i}∪{e|f（e）=i},记C（i）=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat（G）=min{k|G存在k－均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图K t 3、图Dm,4和齿轮图■n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。