几类图的最优填充数

运用图的最优填充分解定理和局部最优填充定理,将一些特殊图类G1×G2,S(G),R(G)和双圈图分解为一些可求得最小填充数的图,得到如下结果:(1)F(Pm×Pn)≤(m-2)(n-2),其中m≥2,n≥2;(2)若G是有m条边的n阶2-连通图,则F(S(G))=m F(G);(3)设图G为双圈图,两个诱导圈的圈长分别为p和q,t为这两个圈公共部分的路上的顶点个数(不包括两个端点),则F(G)=p q-t-6.     

某类二部图的距离谱半径

设Bkn为所有n(n>12)个顶点,k(k>2n/3)条割边的形如Kkm,n的一类二部图的集合,Kkm,n表示把一个星图K1,k(k≥1)的中心和Km,n(m,n≥2)中一个度为n的顶点合并为一个点得到的图。本文讨论了Bkn中取得最小距离谱半径的图所满足的条件。     

有关图(P(1)1∨Pn)∪(P(2)1∨P2n)和(P2∨n)∪Gn-1优美性研究

文章给出了非连通图(P1∨Pn)∪St(m)和(P(1)1∨Pn)∪(P(2)1∨P2n)及(P2∨n)∪Gn-1,证明了对任意自然数n,设s=(n)/(2),则当n≥3,m≥s时,非连通图(P1∨Pn)∪St(m)是优美图;当n≥3时,非连通图(P(1)1∨Pn)∪(P(2)1∨P2n)是s-优美图;当n≥2时,非连通图(P2∨n)∪Gn-1是优美图;其中,Pn是n个顶点的路,P1、P(1)1和P(2)1均是只有一个顶点的平凡图,G1∨G2是图G1与G2的联图,St(m)是m 1个顶点的星形树,Kn是n个顶点的完全图,n是Kn的补图,Gn-1是任意一个n-1条边的优美图.     

具最小度距离的完美匹配单圈图

证明了k≥11时,2k(k∈N)阶具完美匹配的单圈图的最小度距离图是由一个三角形并在三角形一个顶点粘上k-2条长度为2的路和一条悬挂边构成的.     

Bubble-Sort图的限制边连通度

一个图G的限制边连通度是使得G-F不连通且每个分支至少含有2个顶点的最小边子集F的基数.文章中,我们证明当n≥3时Bubble-sort图Bn的限制边连通度λ′(Bn)=2n-4.     

正则图的代数连通度

设G=(V,E)是一个具有n个顶点的简单图,A(G)是G的邻接矩阵,D(G)表示G的度对角矩阵,图G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).若矩阵L(G)的特征值为μ1≥μ2≥…≥μn-1≥μn=0,则称μn-1为G的代数连通度.研究了正则图的代数连通度,得到了下列结论:μn-1≤(nrln(n-l))/(6n-8-4r-nln(n-1))这里,r表示正则图的度.     

单圈图的度距离序

记G(n)为所有n阶连通简单单圈图所构成的集合。主要讨论了G(n)按其度距离从小到大进行排序的问题,并确定了该序的前5个图和相应的度距离。其中极小图是由n阶星图的2个悬挂点之间添加一条边所得到的图R(3)n=3n2-3n-6。n,且D′R(3)     

图的谱半径和泛圈性

设G=(V,E)是一个n阶m条边的简单连通图,μ(G)为图的邻接矩阵的最大特征值。本文利用图的谱条件讨论了图的泛圈性,证明了n(n≥5)阶图G,如果μ(G)n-2,则G是泛圈图除非G=Kn-1+e。     

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

为了讨论给定阶数为n且具有n-4个悬挂点的三圈图补图图类中邻接矩阵的最小特征值,刻画其最小特征值达到极小的唯一图。在只考虑简单无向连通图的基础上,从补图的结构出发研究图的最小特征值,通过运用相关知识点分析论证了当值为λ(G(■(n-4)/2?,?(n-4)/2■)~C)时,给定阶数为n且具有n-4个悬挂点的三圈图补图图类中邻接矩阵的最小特征值达到极小的唯一图。结果表明:结合图邻接矩阵是表示顶点之间相邻关系的矩阵,它的最小特征值为图的最小特征值,较好地刻画图的本质性质。研究得出的具有n-4个悬挂点的三圈图补图的最小特征值达到极小的唯一图,为后续进一步研究补图图类中邻接矩阵的最小特征值提供了一定的借鉴价值。     

两类非连通图优美性的研究

给出了两类非连通图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)和(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1(k=1,2), 并证明了如下结论:对自然数n, m, m1, m2, m3, 设s=〖JB(［〗〖SX(〗n〖〗2〖SX)〗〖JB)］〗, n≥9, m1≥s+2, 则图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)是一个优美图; 对 k=1,2,设n, m≥3, G(k)n-1是一个具有n-1条边的k-优美图,则图(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1是一个优美图。 其中,K2是一个具有2个顶点的完全图,K2〖TX-〗是图K2的补图,K2〖TX-〗∨Cn是图K2和n圈Cn的联图, St(m)是一个具有m+1个顶点的星形树。