仅有三个悬挂点的图的补图的最小特征值

设图G是点集为V(G)＝{v1,v2,…,vn}的简单连通图,则G的邻接矩阵是A(G)＝(aij)n×n,其中若vi和vj相邻,则aij＝1,否则aij＝0.由于A(G)是实对称的,因此可将其特征值设为λ1(G)≥λ2(G)≥…≥λn(G),且A(G)的特征值也称为G的特征值.该文在仅有三个悬挂点的图的所有连通补图中,确定了其最小特征值达到最小值时的唯一图.     

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

研究了当G是连通正则图时 ,其第二大特征值在区间 [0 ,1)上的分布情况。结果表明 ,若G为连通正则图 ,则λ2 (G) <1,当且仅当G为完全等l部图Kp ,p ,… ,p(lp =n)或G =G1 G2 … Gl,其中 Gi 为奇圈 ,1≤i≤l。     

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

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

循环图的Estrada指数

设G是一个具有个n顶点和m条边的简单连通图,A(G)是它的邻接矩阵,其特征值为λ1≥λ2≥…≥λn,图G的Estrada指数定义为EE(G)=∑ni=1eλi.利用算术几何平均不等式,得到循环图的Estrada指数的一个较为精确的上界和下界.     

图中顶点子集的边连通度与最优分级边连通图的构造问题

G =(V ,E)是无向连通图 ,无环允许有重边 .S是V的至少包含两个顶点的子集 ,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数 .给定集合V和V的一个划分V =V1∪V2 ∪…∪Vr(|r|≥ 1,|V1|≥ 2 )以及正整数序列k1>k2 >… >kr≥ 2 .记Si=V1∪V2 ∪…∪Vi,1≤i≤r.构造一个连通图G =(V ,E)满足 :λG(Si)≥ki(1≤i≤r)且边数 |E|最小 .这种图G称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 ,本文提出并讨论了有关最优分级边连通图的构造问题     

变换图G--+的超边连通性

如果λ(G)=δ(G),则称图G是极大边连通的;如果G的最小边割只能分离G的一个孤立点,则称图G是超边连通的.证明了对所有的有限图G,其变换图G-- 都是极大边连通的,G-- 是超边连通的当且仅当G不同构于K1,2也不同构于K2∪K1.     

点可迁图的限制边连通度

对于度k( ≥ 2 )的点可迁连通图的限制边连通度λ′,已知k≤λ′≤ 2k- 2 ,且λ′的界可以达到 .在此基础上 ,对度为k的点可迁图G进一步给出了满足λ′(G) =k的两个充要条件 .接着 ,对任意的连通图G0 证明了λ′(K2 ×G0 ) =min{2δ (G0 ) ,2λ′(G0 ) ,v(G0 ) }.最后证明了对任意满足 0≤s≤k- 3的整数s,存在度为k的点可迁连通图G满足λ′(G)=k s当且仅当k为奇数或者s为偶数     

λ'-最优无三角图的最小边度充分条件

设S是连通图G的一个边割。若G-S不包含孤立点,则称S是G的一个限制边割。图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小度,则称图G是最优限制边连通的,简称λ'-最优的。设G是一个n阶的连通无三角图,且最小度δ(G)≥2.文章证明了,若最小边度ξ(G)≥(n/2-2 )(1+1/δ(G)-1),则G是λ'-最优的。并由此推出,若连通无三角图G的最小度δ(G)≥n/4+1,则G是λ'-最优的。最后给出例子说明这些结果给出的边界都是紧的。     

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

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

具有C-圈逆的K-圈图的刻画

如果图G的邻接矩阵A(G)是非奇异的,那么图G是非奇异的.如果A(G)-1与一个非负矩阵特征相似,那么非奇异图有逆G+.设Η是具有唯一完美匹配的连通二部图.文章给出了Η中具有c-圈逆的k-圈图的刻画(c,k≥1).     

图的广义距离特征值

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

一类二阶迭代泛函微分方程的解析解

在复域C内研究了一类含有未知函数迭代的二阶微分方程λ2x″(z)+λ1x′(z)+λ0x(z)=f(∑mj=0cjxj(z))+G(z)的解析解的存在性。通过Schrder变换,即x(z)=y(αy-1(z)),把这类方程转化为一种不含未知函数迭代的泛函微分方程λ2［α2y″(αz)y′(z)-αy′(αz)y″(z)］+λ1αy′(αz)(y′(z))2+λ0y(αz)(y′(z))3=(y′(z))3［f(∑mj=0cjy(αjz))+G(y(z))］,并给出了它的局部可逆解析解。讨论了双曲型情形0<|α|<1和共振的情形,还在Brjuno条件下讨论了在共振点附近的情形。     

关于图的距离无符号拉普拉斯谱半径的下界

若一个连通图G的点集是V(G)={v1,v2,…,vn｝,那么图G的距离矩阵D(G)=(dij),其中dij表示点vi与vj之间的距离.令TrG(vi)表示点vi到图G中其他所有点的距离之和,Tr(G)表示i行i列位置的元素TrG(vi)的对角矩阵.图G的距离无符号拉普拉斯矩阵QD(G)= Tr(G)+D(G).QD(...     

仅有三个非负特征值的图

假设图G的点集是V＝,用A(G)＝(aij)n×n来表示图G的邻接矩阵,其中,若vi和vj相邻则aij＝1,否则aij＝0.由于A(G)是实对称的,因此可以将其特征值设为λ1(G)≥λ2(G)≥…≥λn(G). 该文刻画了一部分仅有三个非负特征值的图.     

线图的限制性邻域连通度

在间谍工作中,限制性边邻域连通度和限制性邻域连通度比一般连通度和边连通度更加稳定可靠。文中提出了两个新概念:限制性邻域连通度和限制性边邻域连通度。证明了如果图G的线图L(G)是κ’NC图,那么κRNC(L(G))=λRNC(G)当且仅当G不是super-λRNC。并且证明了如果G是λpN C+1,q+1(G)连通图,那么L(G)是κpN,Cq连通的,并且κpN,Cq(L(G))=λpN C+1,q+1(G)。     

强乘积图的连通度和边连通度

研究了两个图G1和G2的强乘积图G1(□×)G2的连通度和边连通度,这里证明了λ(G1(□×)G2)=min{λ1(n2+2m2),λ2(n1+2m1),δ1+δ2+δ1δ2},如果G1和G2都是连通的;还证明了κ(G1(□×)G2)=min{δ1n2,δ2n1,δ1+δ2+δ1δ2),如果G1和G2都是极大连通的.其中,ni,mi,λi和δi分别表示Gi(i=1,2)的阶数、边数、边连通度和最小度.     

两类图的（d，1）-全标号

图G的一个k-（d,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同值,且任一对相关联的点和边的值差的绝对值至少为d．G的（d,1）-全标号数λ^Td（G）定义为G有一个k-（d,1）-全标号的最小的k值,得到了扇图与轮图的（d,1）-全标号数。     

图的独立数与分数一致性

设G是一个顶点集为V（G）,最小度为δ（G）,独立数为α（G）的图, k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V（F）都有dhG（x）＝k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ（ G）≥k＋2,且α（ G）≤4k（δ-k-1）（k＋1）2,则图G是一个分数k一致图。     

一类5—桥图的色唯一性

设P(G;λ）是图G关于变量λ的色多项式。如果对任意图H,P（H;λ）＝P（G;λ）,都有H和G同构,则称图G是色唯一的,由连接两个顶点的s条内部不交的路组成的图叫s-桥图,本文给出了一类5-桥图F（2,2,2,a,b)(a≥b≥3)是色唯一的充分必要条件,推广了关于5－ 图色唯一性的已有结论。λ