一类K-4与路点粘接补图的色唯一性

利用图的伴随多项式的最小极及第四项系数，给出了一类K4^-与路点粘接补图色唯一的充要条件。     

阶数不超过8的标定自补图的计数

标定自补图的计数问题是“组合计数”理论中的难题.本文通过构造出的阶数≤8的全部自补图,计算出每一个自补图的自同构群,获得了顶点数分别为4,5和8的标定自补图的数目分别是12,72和112140.     

全变换图的基本性质

我们引入了四对变换图,其中有一对是全图和它的补图。我们研究这些变换图的基本性质。     

H（r,s）的补图色性

设Pr和Ps分别是两条具有r和s个顶点的路,用K3连接Pr和Ps的两个起点所得到的图,记作H（r,s）。h(G,x）是图G的伴随多项式。作者证明了,如果Pr-1,Ps-1和H（r,s）是不可约的,并且r和s是偶数（r,s≥4）。则H(r,s)的补图是色唯一的。同时还给出了计算伴随多项式的基本公式。     

图上Nordhaus-Gaddum型的符号全控制数的界

函数f:V(G)→{-1,1}称为图G的符号全控制函数,如果对每一个开邻域集上的点的函数值的和都大于等于1.符号全控制函数的权值是指图中所有点的函数值的求和.图的符号全控制数为图中所有符号全控制函数的最小权值.令G表示图G的补图.在该文中,我们研究符号全控制数的Nordhaus-Gaddum型不等式,给出了路与其补图的符号全控制数和的上界,以及图与其补图的符号全控制数和的下界.     

基于圈或路的多重星相关图的生成树数目

利用图的标定技巧、矩阵和行列式运算、补生成树矩阵定理等理论,研究了当图G是基于圈或路的多重星图时,补图类Kn-G的生成树数目的计数问题,得到了一些特殊情况下基于圈或路的多重星相关图的生成树数目的计数公式．     

具有n-3个悬挂点的单圈图补图的最小特征值

特征值的极图问题一直是谱图理论的研究热点,与谱半径相比,最小特征值的研究较少,但图的最小特征值同样能较好地反映图的结构信息,具有很强的研究价值。本文主要讨论给定阶数n且悬挂点为n-3的单圈图补图图类中邻接矩阵的最小特征值,刻画了最小特征值达极小的唯一图。     

图与其补图的独立数之间的关系

文章讨论了图G及其补图(?)的独立数之间的关系,得到的主要结果是a(G) a((?))(?)n 1.     

弦图的补图的最小填充

从图论观点讲,最小填充问题就是在一个图G中添加边集F,使得图G的母图G F是一个弦图而且所添边的边数| F|是最小的,其中最小值| F|称为图G的填充数,表示为f( G) .对一般图来说,最小填充问题是NP-困难的,但是对一些特殊图类来说,这个问题是在多项式时间内可解的.本文给出了弦图的补图-G的填充数f(-G) .     

森林补图的最小填充

本文研究森林补图的最小填充问题,并给出了森林补图的填充数的表达式.