具有较大四独立集的色唯一的三部图

设G是简单图,■表示图G的补图,用P(G,λ)表示图G的色多项式.若P(G,λ)=P(H,λ),则称G与H是色等价的,简记为H～G.令[G]={H|H～G}.若[G]={G},称G是色唯一的.设K_(n,n,n)是一个完全三部图且各部分顶点数均为n.图G=K_(n,n,n)-S表示从完全三部图K_(n,n,n)中删去边集S所得的图.本文证明了一些具有较大四独立集的三部图是色唯一的.     

若干图的倍图的邻点可区别边(全)染色

设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ’as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。     

（P,P）图的可嵌性定理

设G是一个简单无向图,称G是(P,P)图,如果|E(G)|=|v(G)|.若G同构于6某个子图,则称G可嵌入6,本文用极其简捷的方法证明了:阶数大于9的(P,P)图可嵌入其补图内的充要条件是G不和图(1)中的任一个图同构。     

两类图及补图的匹配惟一性

设G是简单图,用μ(G,x)表示图G的匹配多项式,若μ(G,x)=μ(H,x),则称G与H是匹配等价的,记为H~G.若H~G可导出H G,则称图G是匹配惟一的.在此基础上研究了T形树的匹配惟一性,证明了T(m,m 1,m 2),T(m,m 1,m 3)(m≥1)及补图是匹配惟一的.     

具有5n+4个点的5部图的色性

设G是简单图，用P(G，λ)表示图G的色多项式，若P(G，λ)=P(H，λ)，则称G与H是色等价．令H～G，令{G}={H|H～G)，若对任意的图G有{G}={G}，称G是色唯一的．设G表示具有5n 4个点的完全5部图，令θ(G)=(m5(G)-2^n 2-2^n-1 5)／2^n-1，其中m5(G)表示G的6-独立分划个数．本文证明了θ(G)≥0且刻划θ(G)=0，1，3／2，2，5／2，13／4的图．利用此结果研究了图G—S的色性，其中S是图G某些边组成的集合，G—S表示从G中删去S中所有的边得到的图，进而得到许多色唯一的5部图．     

图与补图孤立断裂度的关系

连通图G的孤立断裂度isc(G)=max{i(G-S)-｜ S ｜:S∈C(G)},其中i(G-S)是G-S中的孤立点数,C(G)是G的点割集.文章研究了图与补图孤立断裂度的关系.     

■图的色唯一性

设G是简单图,用P(G,λ)表示图G的色多项式,若P(G,λ)=P(H,λ),则称G与H是色等价的,简单的表示为H~G.记[G]={H|H~G}.若[G]={G},称G是色唯一的.本文给出了(∪iCi)∪(∪jDj))图色唯一的相对于文献[1]、[2]中的结论更为一般的结论.     

Δ(G)=2的图的孪生强边染色

设σ是一个阶至少为3的简单连通图G的k-正常边染色,其中颜色集合为{0,1,2,…,k-1}.若对任意距离不超过2的两条边e,,存在σ(e)≠σ(),则称σ为G的强边染色.若图G的强边染色σ能够诱导一个G的2-距离点染色,则称σ是G的孪生强边染色.最少的颜色数为G的孪生强边色数,记为■_(s,t)(G).通过研究简单连通图的孪生强边染色,得到了相应的染色数.     

(∪iCi)∪(∪jDj)图的色唯一性

设G是简单图,用P(G,λ)表示图G的色多项式,若P(G,λ)=P(H,λ),则称G与与H是色等价的,简单的表示为H～G.记[G]={H|H～G}.若[G]={G},称G是色唯一的.本文给出了(∪iCi)∪(∪jDj))-图色唯一的相对于文献[1]、[2]中的结论更为一般的结论.     

单圈图的Seidel无符号拉普拉斯能量

设G是一个具有n个顶点、m条边的简单图,S(G)表示G的Seidel矩阵,d_i表示顶点v_i的度,又以DS(G)=diag(n-1-2d_1,n-1-2d_2,…,n-1-2d_n)来表示对角矩阵,再依次定义图G的Seidel拉普拉斯矩阵为SL(G)=DS(G)-S(G)、图G的Seidel无符号拉普拉斯矩阵为SL~+(G)=DS(G)+S(G)和图G的Seidel无符号拉普拉斯能量为■,这里σ1L+,σ2L+,…,σnL+为矩阵SL+(G)的特征值.文章利用不等式讨论单圈图G的Seidel无符号拉普拉斯能量的上界,得到了几个有意义的结果.     

2-重自补图和有向自补图的几个性质

本文讨论了2-重自补图和有向自补图的连通性以及2-重自补图的直径,同时以自补置换作为工具研究了当2-重自补图或有向自补图被分成两个连通分支后,这两个连通分支之间的边数与顶点数之间的关系.     

论自补图的构造(Ⅱ)

通过剖析4n阶和4n+1阶自补图之间的关系,应用度序列的方法,以4n阶自补图为基础,给出了构造4n+1阶自补图的递推方法。     

具有多个强正则自补图的最小阶数

本文应用两个不同构的13阶强正则自补图,解决了Kotzig在1979年提出尚未解决的问题:“至少存在两个非同构的4k 1个顶点的强正则自补图集中,其最小整数k是什么?”,获得了最小整数k=3,并且否定了Kotzig在这个问题上所获得的结果.     

关于几种自补图的直径

本文给出了三种类型的自补图关于直径方面的结果,并从自补图的邻接矩阵给出了自补图直径为2或3的一个充要条件.     

自补图的独立数与覆盖数

主要讨论了自补图的边独立数和边覆盖数,给出了点独立数的严格上、下界： ,其中 是 的点色数,分析并证明了点独立数取得上、下界的自补图的存在性。     

自补图的构造理论与构图

提出并证明了几个自补图的构造命题，探讨了自补图的构造方法。完成了９个点以内的所有自补图构图，并对１２个点的自补图的构图进行了初步探讨。     

5个顶点所有136个有向自补图的构造

Ｒｅａｄ在１９６３年就算出５个顶点的有向自补图共有１３６个，但这些图一直未被全部构造出来，本文应用２－重自补图的结果，构造出了１３６个有向自补图．     

自补图的平面性讨论

分析探讨了所有自补图的平面性及外可平面性，得出了v≤8的自补因是可平面的；v≤5的自补图是外可平面的。     

图的广义距离特征值

图G的广义距离矩阵定义为D_α(G)=αTr(G)+(1－α)D(G),0≤α≤1,其中D(G)和Tr(G)分别表示图G的距离矩阵和传递度对角矩阵.研究了广义距离相关谱,给出了其谱半径、第二大特征值的界,及自补图的广义距离谱.     

A·Kotzig关于自补图猜想的新结果

主要给出：Ｇ≌ｆＧ,ｆ＝π１π２…πｍ,π１,π２,…,πｍ是ｆ互不相交的轮换,则｜πｉ｜＝１或｜πｉ｜＝０（ｍｏｄ４）。