3-正则图的上控制数和上无赘数相等的禁止子图条件

在文献[1]中，Cockayne和Mynhardt反证了Henning和Slater的一个猜想：任一个3－正则图G有IR（G）＝Γ（G）。在这篇文章中，我们给出了一正则图的Γ（G）＝IR（G）的禁止子图条件。     

K顶边星图的优美性

文[1][2]分别给出了轮图和齿轮图的优美性，本文证明了在齿轮图（n为奇数）每个齿的顶端联结k条长度为1的边所得图是优美的，从而得到文[3]所提猜想的一个结果。     

三个5-阶图与圈Cn联图的交叉数Cn

联图G∨H表示将G中每个点与H中的每个点连边得到的图．在Klesc M给出所有3阶图和4阶图与圈Cn联图的交叉数的基础上,利用反证法和排除法确定了G1,G2,G3三个5-阶图与圈Cn联图的交叉数,他们的交叉数分别是cr（G1∨C2）=Z（5,n）＋2[n/2]＋2,cr（G2∨Cn）=Z（5,n）＋2[n/2]＋2,cr（G3∨Cn）=Z（5,n）＋2[n/2]＋3.     

完全三部图K(n-4,n,n)的色唯一性

设G是简单图,用P（G,λ）表示图G的色多项式．若对任意图H使P（H,λ）＝P（G,λ）,都有H与G同构,则称G是色唯一图．用K（m,n,r）表示完全三部图,证明了当K＝4时,如下猜想[1]成立：对非负整数n,k,当n≥k＋2时,K（n－k,n,n）是色唯一图．即当n≥6时,K（n－4,n,n）是色唯一图．     

关于Catlin—猜想的反例

Catlin的2／3－猜想：若G是超欧拉图，G≠K1，那么G有一个欧拉生成子图H，使得|E(H)|≥2／3|E(G)|。给出了Catlin的2／3－猜想的一些反例。     

（UiCi）U（UjDj）图的色唯一性

设G是简单图，用P（G，λ）表示图G的色多项式，若P（G，λ）=P（H，λ），则称G与H是色等价的，简单的表示为H-G．记[G]={H／H-G}．若[G]={G}，称G是色唯一的．本文给出了（UiCi）U（UjDj）图色唯一的相对于文献[1]、[2]中的结论更为一般的结论．     

关于图的边添加和减少

用P（t，d）（或者C（t，d））表示从长为d的路（或者圈）通过添加t条边后得到的图的最小直径，Tp（p，d）（或者Tc（p，d））表示为了得到直径最多为p的图需要向长为d的路（或者圈）中添加的最少边数，f（t，d）表示从直径为d的图中删去t条边后得到的连通图的最大直径．我们给出了这些参数新的上下界．特别地，证明了Grigorescu[J．Graph Theory，2003，43（2）：299—303]猜想：Tc（3，d）=d-8，其中d≥12；并且部分地解决了Schoone等人[J．Graph Theory，1987，11（13）：409—427]的猜想：f（t，d）≤（t＋1）d-t＋1．     

2-连通 [5,3]-图中的Hamilton圈

如果G中任意s个点的导出子图中至少含有t条边，则称图G为[s，t]-图，证明了若G是顶点数不小于8且δ（G）≥3的2-连通[5，3]-图，则G含有Hamilton圈．     

Sampathkumar猜想的证明

设x_k(G)表示图G 的P_k-色分划数,本文证明了Sampathkumar 等在文献[2]中提出的一个猜想,即对任何P 阶图G,都有X_k(G)+X_k(■)≤t+1,X_k(G)+X_k(■)≤((t+1))/2)~2,这里t={p/k}.     

关于连通图端片的一些结果

设G=(V，E)为简单连通图，A包括V．G[A]称为G的断片，如果存在极小割S，使得G[A]是G—S的分支．G[A]称为G的端片，如果G[A]为G的断片，且对A的任何真子集B，G[B]不是G的断片．给出G的端片的一些性质，得到端片个数∑≤|V|的结论，并给出等号成立的一些必要条件及充分条件．