C2j+1∪C2k类与Pk n类调和图

证明了Ｓｅｏｕｄ等当ｋ≥３时Ｃ３与Ｃ２ｋ的不相交并Ｃ３∪Ｃ２ｋ为调和图的猜想,并扩展该结果,证明了Ｃ５∪Ｃ２ｋ（ｋ≥２）是调和图;给出猜想Ｃ２ｊ＋１∪Ｃ２ｋ（ｊ≥１,ｋ≥２且（ｊ,ｋ）≠（１,２）是调和图。证明了幂图Ｐ＾４ｎ（８≤ｎ≤１７）与Ｐ＾５ｎ（１４≤ｎ≤１７）是调和图,否定了Ｓｅｏｕｄ等关于当且仅当１≤ｋ≤３时Ｐ＾ｋｎ（１≤ｋ≤ｎ－１）是调和图的猜想。给出了相反的猜想：当ｎ≤ｎ０（ｋ）时Ｐ     

路和回路的各种乘积图的联结数

图的联结数是图的示性数之一．Ｄ．Ｒ．Ｗｕｏｄａｌｌ［１］首先引进了这个概念，研究了联站数与 图的其它量之间的关系．Ｖ．Ｇ．Ｋａｎｅ，Ｓ．Ｐ．Ｍｏｈａｎｔｙ和Ｒ．Ｓ．Ｈａｌｅｓ［２］研究了一些乘积图 的联结数．［３］中证明了［２］中提出的关于ｂｉｎｄ（Ｃｍ×Ｃｎ）的猜想．本文进一步研究了［２］、［３］未 解决的若干乘积图的联结数，得到了Ｌｍ×Ｃｎ，Ｃｍ　Ｃｎ，Ｌｍ　Ｃｎ，Ｃｍ＊Ｃｎ，Ｌｍ＊Ｃｎ，Ｃｍ（Ｃｎ），Ｌｍ（Ｃｎ）等图的联结数。     

关于图的圈覆盖

Ａ．Ｉｔａｌ和Ｍ．Ｒｏｄｅｈ给出了两个关于图的圈覆盖的猜想：（ｉ）任意２－边连通图Ｇ＝（Ｖ，Ｅ）有困覆盖Ｃ，使ｌ（Ｃ）≤｜Ｅ｜＋｜Ｖ｜－１；（ｎ）任意２－边连通图有困覆盖，使图的每条边至多被覆盖两次．本文证明了猜想对平面图和２－边连通没有３－边割的图成立，并给出了一与两猜想等价的条件．同时也对著名的２－圈覆盖猜想作了讨论．     

Ore k-型图的性质和1-因子

本文研究了 Ｏｒｅ ｋ－型图的若干表征其结构的性质，并证明了 Ｏｒｅ ｋ－型图 Ｇ在 δ（Ｇ）＝ｋ＋２≤ｎ＋１或δ（Ｇ）≥ｎ＋ｋ的条件下含有ｋ＋２个边不重的１－因子．从而部分地证实了Ｗｉｎ 猜想．     

O（4）包含O（3）的旋表示约化因子

利用不可约张量基的概念和不可约张量算符的性质，给出了Ｏ（４）包含Ｏ（３）的约化因子（ｎ１，ｎ２）强乘积（１／２±１／２）的代数表达式，同时也给出了Ｏ（４）Ｒａｃａｈ系数（１／２１／２）强乘积（ｎ１，ｎ２）强乘积（１／２±１／２），（１／２±１／２）强乘积（ｎ１，ｎ２）强乘积１和（ｎ１，ｎ２）强乘积（１／２±１／２）强乘积１的代数表达式。     

n拟偶图的全色数

引入ｎ拟偶图，对ｎ≤３时当ｎ〉３时，剖分边集导出子图为道路，圈、Ｋ１３的细分图或Ｋ１．３＋ｅ的细分图等情形证明了全着色猜想。     

关于CockayneEJ的两个猜想

猜想１〔１〕当Ｋ（Ｇ）＝Ｃ２ｎ＋１时有Ｃ（Ｇ）≤ｄ（Ｇ）;猜想２〔１〕当Ｋ（Ｇ）是偶图时有Ｃ（Ｇ）≤ｄ（Ｇ）．以下通过反例说明猜想１不成立．然后证明猜想２成立．设Ｇ是无向、无环、无多重边的简单图,Ｇ＝（Ｖ,Ｅ）,其中Ｖ＝Ｖ（Ｇ）表示Ｇ的顶点集,Ｅｎ＝...     

关于K_（1，2，n）和K_（1，1，1，n）的优美性

分别给出了完全３部图Ｋ１，２，ｎ和完全４部图Ｋ１，１，１，ｎ的一种优美标号，从而证明了Ｋ１，２，ｎ和Ｋ１，１，１，ｎ是优美图．     

一类高度图的均匀色数

Ｗ．Ｍｅｙｅｒ猜想,设ｎ阶通图Ｇ的最大度为△（Ｇ）,且Ｇ不为完全图和奇圈,则图Ｇ的均匀着色数Ｘｅ（Ｇ）≤△（Ｇ）。本文证明了当△（Ｇ）≥ｎ－３时,此猜想成立。     

方格偶图Bm×n中的圈数

设Ｂ_(ｍ×ｎ)是具有ｍ×ｎ个顶点的方格偶图,ｇ（ｍ,ｎ）表示图Ｂ_(ｍ×ｎ)中不同圈的数目．证明了 ｇ（２, ｎ）＝ ｎ（ ｎ＋ １）／２, ｇ（３, ｎ）／２＝［（１＋√２）（ｎ＋２）＋（１－√２）（ｎ＋２）］／４－ ２（ ｎ－ １）－ ７／２,其中 ｎ＝２,３,４,…     

至多有2个等长圈的简单图的最大边数

设Sn是具有n个顶点至多有2个等长圈的简单图的集合。若Sn中不存在图G’使|E(C’)|>|E(G)|,Ng称G是简单的最大图分布(2)图(简记为简单MCD(2)图)。用f~*(n,2)表示具有n个顶点的简单MCD(2)图的边数。作者证明了f~*(n,2)≥(n-l)+[1/2(11n-20)~(1/2)]且当3≤n≤10时等式成立。     

一类正则图的邻强边染色

研究一类正则图G(n,n,r)(n=1,2(mod 3))的邻强边染色. 用构造性方法给出了一类正则图的邻强边染色, 验证了对|V(G)|≥3的连通图G（V,E）(G(V,E)≠C₅), 有Δ(G)≤χ′_αs(G)≤Δ(G)+2成立.     

RP图的特征刻划

设T是图G的一颗支撑树,若某顶点u满足;对任意顶点υ均有dG(u,υ）=dT(u,υ）,则称u对于支撑树T是RP,如果对G的任一棵支撑树都至少存在一个RP点,则称图G是RP图,Gagliardi等在1997年证明了K2,n是一类RP图,并猜想：“K2,n以及在其顶点上加上若干树状结构所得的图是仅有的RP图”。但容易验证圈Cn也是一类RP图,因此上述猜想需要修正,本文证明了RP图的如下特征刻划：除树外,简单图中只有K2,n和Cn 以及在某若干顶点上分别外接互不相交的树状结构所得的图是RP的。     

两类二面体群的三度Cayley图的比较

对4m阶拟二面体群G=〈a,b｜a2m=b2=1,ab=am＋1〉和4阶半二面体群G=〈a,b｜a2m=b2=1,ab=am-1〉且m=2r,r〉2的3度Cayley图作比图。得到两者均有一个图是正规Cayley图且同构,且A1≌Z2的结论。     

超立方图和超立方有向图的同构因子分解

图Ｇ＝（Ｖ，Ｅ）的一个同构因子分解是边集Ｅ的一个划分：｛Ｅ１，Ｅ２，…，Ｅｔ｝，使得生成子图（Ｖ， Ｅ１），…，（Ｖ，Ｅｔ）都彼此同构。若 Ｈ≌（Ｖ，Ｅ１），记为 Ｈ［Ｇ或 ｔ］Ｇ．若对每个ｔ≥２．当　　　时．均有：ｔＧ，则称Ｇ为有理图．文章证明了超立方图（ｈｙｐｅｒｃｕｂｅ）和超立方有向图都是有理图．     

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

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设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的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。     

刺图乘积上的Graham猜想

 证明了对于一个完全图的刺图和一个具有2-pebbling性质的图,Graham猜想成立。作为一个推论,当G和H均为完全图的刺图时,Graham猜想成立。     

关于跳跃图的一点注记

图G的跳跃图记作J(G),其定义为：V(J(G))=E(G),ef∈E(J(G))当且仅当e、f在G中不相邻,该文证明：若G=(V,E)是不含孤立点的图,阶P≥q,边数q≥5且△(G)≤q／2,则除一类特殊图外,J(G)是H-图．从而否定Gary Chartand等人提出的一个猜想．     

关于有限内循环群边传递的图

所指的图是有限的、单的、无向的且无孤立点,p,q,t是素数,m,r是正整数且满足r■1≡rq(modp).获得了关于有限内循环群边传递的图的完全分类,结果为:设Γ是一个图,G是一个阶为pqm或t2或8的内循环群,且G≤Aut(Γ),则Γ是G-边传递的当且仅当Γ同构于下列图之一:(1)qm-eCpqe,0≤e1;(4)pCqm,(q,m)≠(2,1);(5)pK1,1,m=1;(6)Cay(Zp,C),C={±rμ|μ∈Zq},m=1;(7)B(Zp,C),其中C={1-rj|j∈Zq},m=1;(8)Kp,1,m=1;(9)pKqm,1;(10)Kpqm,1;(11)Kqm,p;(12)pqeK1,qm-e,1≤e≤m;(13)qeK1,pqm-e,1≤e≤m;(14)qeKqm-e,p,1≤e2;(16)2K1,1,t=2;(17)t2K1,1;(18)tKt,1;(19)Kt,t;(20)Kt2,1;(21)2C4;(22)8K1,1;(23)2K4,1;(24)4K2,1;(25)K8,1.     

关于 Randic 指数及图的直径

设图G=(V , E)是简单图,其中V是顶点集,E是边集.对G中任意顶点v∈V, dv表示点v的度数.图G的Randic指数也称为图G的连通性指数,定义为R=R(G)=∑uv∈E(1)/(dndv).关于连通图的Randic指数R与直径D有如下猜想:R-D≥2-(n+1)/(2)且(R)/(D)≥(1)/(2)+(2-1)/(n-1),两个等式都成立当且仅当G≌Pn.本文将简化该猜想,并进一步证明当D≤(2(n-1)(3)/(2))/(n-3+2 2)或D≤n-3时,猜想成立