L*n,p图的全匹配数

设Kp是p阶完全图。 取Kp的任意r个顶点分别点粘接r颗树,所得到的n阶图集记为L*n,p。 确定了L*n,p中具有最大和最小,第二大和第三大全匹配数的图。     

图的代数连通度及其点连通度

G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.     

Nordhaus-Gaddum型的代数连通度的界

对任一个n阶单图G,用a(G)表示G的代数连通度,Gc为G的补图.通过代数连通度与Laplacian谱半径的关系,给出了几类图的Nordhaus-Gaddum的代数连通度的和的界.     

具有相同基础图的一类混合图的特征值

设G为n阶连通混合图.当G为非奇异,其最小非零特征值为λ1(G)>0.给G的每条无向边指定任意一个方向,得到与G有相同基础图的全定向图G,则G的最小非零特征值为其代数连通度(或次小特征值)λ2(G)=α(G)>0.本文主要讨论λ1(G)与α(G)的关系,证明了:当G恰含一个非奇异圈,有λ1(G)≤α(G).     

关于图的代数连通度的注记

n阶连通图G的代数连通度、点连通度和边连通度分别记作α(G) ,κ(G)和λ(G) .本文给出了当 2 κ(G) n- 2时 ,α(G) =κ(G)成立的充要条件 ,讨论了α(G)的代数重数以及相应于特征值α(G)的特征向量的性质 .最后给出了当 1 λ(G) n- 2时 ,α(G) =λ(G)的充要条件 .     

3p2阶连通4度Cayley图的正规性

对于一类3p2(p是素数)阶群G=1,r3≡1(mod p)>,研究了其连通4度Cayley图的正规性,并通过其点稳定子的结构证明G的连通4度Cayley图均正规.鉴于王艳丽等人的相关工作,这等于圆满解决了3p2阶群的连通4度Cayley图的正规性问题.     

双圈图的N-G型的代数连通度的界

对任一个n阶单图G,用a(G)表示G的代数连通度,GC表示它的补图.针对双圈图,即边数等于顶点数加1的且只含有2个边不交的基本圈的简单连通图,证明了对任一n阶双圈图G,有1≤a(G)+a(GC),当且仅当G≌G1时等式成立.     

给定匹配数的图的代数连通度的上界

【目的】确定给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图。【方法】首先，利用图的匹配数与奇连通分支个数的关系与图的变换等方法刻画了给定匹配数的n个点图的拉普拉斯代数连通度上界所对应的极图；其次，利用具有相同邻点集的图与对应特征值的关系得到给定匹配数的n个点图的拉普拉斯代数连通度上界。【结果】借助图与补图的关系以及拉普拉斯特征方程证明得到给定匹配数的n个点图的拉普拉斯代数连通度的上界与该上界所对应的极图是一一对应且唯一确定的，从而同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图。【结论】用全新的方法同时确定了给定匹配数的n个点图的拉普拉斯代数连通度的上界以及此上界所对应的极图，克服了以往利用图的最小度，最大连通度与代数连通度的关系只刻画了给定匹配数的图中具有最大代数连通度的图类特征，但无法得到此类图的连通度的上界这一弊端。     

树的移接变形与代数连通度

讨论了树的代数连通度.利用移接变形给出树的代数连通度的一种变化关系,同时给出了两类树的代数连通度与直径的关系.     

给定直径的图的Wiener指数逆问题

图的Wiener指数逆问题在生物医学中具有重要的研究意义,对有目的地合成药物有重要的理论指导价值.研究一类给定直径的连通图的Wiener指数,讨论和刻画直径为d的n阶连通图中具有最小Wiener指数的图,并且对于不小于r_1任意正整数r,能构造一个直径为d的n阶连通图,使得它的Wiener指数为r.     

含有两个基本圈的简单图的N-G型代数连通度的界

对任一个n阶简单图G,用a（G）表示G的代数连通度.在已有文献研究的基础上,通过分类研究和个别图具体研究,证明了对任一含有两个基本圈的简单图G,有1≤a（G）＋a（Gc）.     

正则图的代数连通度

设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表示正则图的度.     

含Cn-1图关于Wiener指数、Harary指数、hyper-Wiener指数的充分条件

拓扑指数和谱理论是图论研究的两个分支.可以用拓扑指数来刻画图的性质,首先分别给出n阶简单图,n阶2-连通图含有Cn-1的边条件的相关引理,然后利用Wiener指数、Harary指数和hyper-Wiener指数分别给出n阶简单图,n阶2-连通图含有Cn-1的充分条件.     

完全二分图上星博弈的一个公式

给出了在完全二分图Kp,p上星博弈时一方成功数a2(K1,n)的定义:甲乙二人在完全二分图Kp,p上博弈,首先甲用绿色对Kp,p的一条边染色,接着乙用红色染Kp,p的另一条无色边,如此甲乙交替地对Kp,p的无色边进行着色.若甲在Kp,p上染成绿星K1,n,且乙在Kp,p上还没有染成红星K1,n,甲胜.否则甲负乙胜.甲能取胜的最小值p=p(n)称为K1,n的一方成功数,记成a2(K1,n).证明了a2(K1,5)=7.     

具有固定顶点的树的代数连通度

设G是一个n阶简单连通图,图G的邻接矩阵记为A(G),令D(G)是G的顶点度对角矩阵,定义G的拉普拉斯矩阵L(G)=D(G)—A(G),设L(G)的特征值为λ_1≥λ_2≥…≥λ_(n-1)≥λ_n=0.在本文中,采用移接变形方法,讨论了树的代数连通度和直径之间的关系,获得了下面的结论:当树的顶点数固定时,树的代数连通度随着树的直径的增加而减少.进一步地,利用Cauchy-Schwarz不等式,讨论了树的代数连通度的界.     

对图的最大Laplace特征值上界估计的两个新结果

设G是n阶简单连通图，其对应的Laplace矩阵的最大特征值记为λ1（G），给定图G的度序列d1≥d2≥…≥dn,我们给出了对λ1（G）的上界估计的两个新结果，并且刻画了等式成立时图的结构特征。     

每点都与3度点相邻的最大临界3棱连通图的结构

没G=(V,E)是3棱连通图,若对每个x∈V(G),G-x 不是3棱连通的,则称G 为临界3棱连通图.p 阶临界3棱连通图的全体记为(?)_3(p),G∈(?)_3(p)称为最大的,如果不存在H∈(?)_3(p),使|E(H)|>|E(G)|.本文给出每个点都与3度点相邻的p 阶最大临界3棱连通图的结构.     

圈长和顶点数给定的单圈图的Laplace 谱半径排序

只含一个圈的简单连通图称为单圈图.郭继明给出了固定圈长的单圈图的Laplace谱半径并刻画了相应的极图.该文在此基础上确定了圈长为g的所有n=g+k(g≥5,k≥3)阶单圈图的Laplace谱半径从大到小的前[g/2]个图.     

本原指数为3的竞赛图的刻划

给出本原指数为 3的 n阶 ( n≥ 5)强连通竞赛图的刻划 .同时结合 n阶竞赛图 D的 min{δ-,δ+ }值的分布情况 ,给出 n阶竞赛图满足 r( D) =3的两个充分条件     

正则图的第二大特征值的分布

研究了当G是连通正则图时,其第二大特征值在区间[0,1)上的分布情况,结果表明,若G莱连通正则图,则λ2（G)＜1,当且仅当G为完全等l部图Kp,p,…,p（lp=n）或G＝G1△↓G2△↓…△↓,其中G^-i为奇图,1≤i≤l.