两类图并补图的色唯一性

刘儒英介绍了图的特征标R(G),并分别给出当R(G)=0和R(G)=1时图类所具有的性质并对图类进行描述,本文推广此结果,讨论了R(G)=-1和R(G)=-2时的情形,并证明了两类具备一定性质的图并的补图的色唯一性.     

关于图与其补图谱半径之和的上界

设G为n阶简单连通图,Gc为G的补图,ρ(G)和ρ(Gc)分别为图G和Gc的邻接谱半径.本文给出了图与其补图谱半径之和ρ(G)+ρ(Gc)的上界,从而改进了已有的结果.     

有向图和弱正则有向图补图的特征多项式的计算方法

本文解决了一般有向图的特征多项式的图论计算方法,并且给出了弱正则有向图和它的补图之间特征多项式的关系,从而也就解决了非负整数方阵特征多项式的图论计算方法问题。     

图与其补图谱半径之和的新上界

该文给出了图与其补图谱半径之和ρ(G)+ρ(Gc)的新上界,对任一n阶图G,有:p(G)+p(GC)≤((2-1/t)n(n-1))和p(G)+p(GC)≤((2-1/T)n(n-1))其中t=min{k,(k-)},T=max{k,(k-)},k,(k-)分别为图G和其补图Gc的色数.从而改进了[6],[8],[10]的结果.     

完全超紧图

Chia G.L.和Lim C.K.在东南亚第一次图论会议(1983,新加坡)文集的末尾提出六个未解决问题.第五个问题是:设H是自补图,问是否存在自补完全超紧图G,使G~*=H.第六个问题是:设G是完全超紧图.如果G_0与(?)同构,问G是否自补图.本文肯定地回答了第五个问题和否定地回答了第六个问题.     

8个顶点的所有10个自补图

本文应用度序列的方法及自补置换圈的有关结果,构造出了8个顶点的全部10个自补图。     

补图具有悬挂点且连通的图的最小特征值

图的最小特征值定义为图的邻接矩阵的最小特征值,它是刻画图的结构性质的重要参数.在给定阶数且补图为具有悬挂点的连通图的图类中,刻画了最小特征值达极小的唯一图,并给出了这类图最小特征值的下界.     

关于有向自补图的构造（Ⅱ）

设Ｄ是有向自补图,Ｖ（Ｄ）＝｛１,２,…,ｎ｝,Ｄ与Ｄｃ之间的同构映射可以表示为Ｖ（Ｄ）上的一个置换σ,记为σ（Ｄ）＝Ｄｃ．若把置换写成不相交轮换的乘积,且σ１和σ２有相同的轮换结构,就有｛Ｄ｜σ１（Ｄ）＝Ｄｃ｝＝｛Ｄ｜σ２（Ｄ）＝Ｄｃ｝．因此,如果对具有不同轮换结构的ｎ阶置换σ,能构造出∪σ｛Ｄ｜σ（Ｄ）＝Ｄｃ｝,就可以构造出所有ｎ阶有向自补图．本文给出了有向自补图的构造方法,并讨论了有向自补图的结构性质．     

图的全局2-彩虹控制的一个注记

为了研究树T的全局2-彩虹控制数γ gr2 (T)与2-彩虹控制数γ r2 (T)间的关系，分析了图的结构，采用分类讨论法和反证法，完全刻画了γ gr2 (T)=γ r2 (T)+1成立的直径等于5的所有树T，解决了Amjadi等人2017年未解决的问题。