基于圈收缩的图的(Sum-)Balaban指标

连通图G的Balaban指标(也叫J指标)的定义是■连通图G的Sum-Balaban指标定义为■其中m,n分别是图G的边数和点数,σ_G(u)表示G中从顶点u到其它各个顶点的距离之和. Balaban指标和Sum-Balaban指标被广泛应用于QSAR和QSPR的研究.证明了:经过圈收缩后,一类单圈图的Balaban指标和Sum-Balaban指标是增大的.观察Balaban指标和Sum-Balaban指标在圈收缩操作中的变化规律,对这两类拓扑指标提出了一种新的比较方法.     

基于圈收缩的单圈图的Balaban指标

令G是顶点集为V(G)和边集为E(G)的一个简单连通图,其顶点数为n,边数为m.图G′则是通过对图G中的圈进行收缩而得到的.Balaban指标被广泛应用于各种QSAR和QSPR的研究.本文分别计算了图G和G′的Balaban指标,并经过比较得出图G的Balaban指标大于图G′的Balaban指标.     

图的强彩虹连通数

如果图G的任意两个顶点由一条路P连接,其中路P的每一条边着不同的颜色,则称图G为彩虹连通图.对图G的任意两个顶点u和v,G的彩虹u-v测地线是一条长为d(u,v)的彩虹路,其中d(u,v)表示最短的u-v路的长度.图G称为强彩虹连通的如果对G的任意两点u和v间都存在一条彩虹u-v测地线.图G的强彩虹连通数是指使得图G是强彩虹连通而用的最少颜色的数目,用src(G)表示.该文首先给出了一个含边不交的k-圈图的一个强彩虹连通数的上界.接着给出了这个上界取等的充分条件.     

关于图的距离控制数的上界

对于任意的正整数l,连通图G的顶点子集D被称为距离l 控制集 ,是指对于任意顶点v D ,D中至少含有一个顶点u ,使得距离dG(u ,v) ≤l.图G距离l 控制数γl(G)是指G中所有距离l 控制集的基数的最小者 .确定图G的距离l 控制数γl(G)是NP 问题 .给出了当G是阶数为p (p ≥l 1 )的连通图时 ,对于任意的正整数l,都有最优上界γl(G)≤ p-Δ l - 1 l .而且针对某些Δ和l,是对Meir和Moon的结果的一种改进     

图的拉普拉斯谱半径的新可达上界

设G是n阶简单连通图,顶点度序列为d1≥d2≥…≥dn.本文利用矩阵变换的方法给出了图G的拉普拉斯谱半径的新上界,并证明了达到该上界的极图仅有正则二部图或星图.同时还证明了在一定条件下,该上界改进了Li,Liu和Shu等人同类的结论.     

连通图平均距离的界

图的距离和是指连通图中所有顶点间的距离之和,与之密切相关的另一个参数是平均距离,它是指连通图的距离和的平均值。连通图的σ(u)指标定义为图中顶点u与图中所有顶点间的距离之和。利用图的σ(u)指标得到了连通图的平均距离的若干上下界,这些界与图的顶点数、边数、直径和半径等密切相关。     

三类正则图的Balaban指标

Balaban指标作为一类重要的图的拓扑指标,被广泛应用定量结构-活性相关(quantitative structure-activity relationship, QSAR)和定量结构-性质相关(quantitative structure-property relationship, QSPR)的各方面研究。给出了正则图Balaban指标的一个下界,然后分别给出小世界网络图、K_2×C_t卡氏积,以及在K_2×C_t卡式积的基础上构造了一类4-正则图的Balaban指标计算公式。     

2-连通图的修正的彩虹顶点连通数

路P称为修正的顶点彩虹路,如果P中所有的顶点着不同的颜色或者除端点外其余顶点着不同于端点的颜色。图G称为是修正的彩虹顶点连通的,如果对于G的任意两个顶点u和v,G都有一条修正的彩虹顶点u-v路。使图G是修正的彩虹顶点连通图的最小颜色数目k称为图G的修正的彩虹连通数,记做rvc*(G)。给出了2-连通图G的修正的彩虹顶点连通数的一个上界,即rvc*(G)≤|n/2|+1。     

一类强定向的最小平均距离

用σ_G(v)表示图G中顶点v与G中所有顶点间的距离之和.利用σ_G(v)指标得到了含有割点的2-边连通图G的强定向的最小平均距离的若干下界.     

冒泡排序图的超带性

图G的k-路集C(u,v)是连接G中顶点u和v的k条内点不交的路的集合.图G的k-路集C(u,v)是一个k*-路集如果连接顶点u和v的k条内点不交的路包含G中所有的顶点.一个二部图G是k*-带的若G中任意两个属于不同二划分集的顶点之间存在k*-路集.设κ(G)是图G的连通度.一个二部图是超带的若G是i*-带的,1≤i≤κ(G).n维冒泡排序图Bn是二部图,是n-1正则的,有n!个顶点.在本文中,首先证明了Bn是(n-1)*-带的,n≥5,然后得到n维冒泡排序图Bn(n≠3)是超带的.     

一类图的次小与第三小能量

图的能量记为E(G),它等于G的特征多项式特征根的绝对值之和.μn表示连通的(n,n)-图(n个顶点,n条边的连通图).对于G∈μn:如果对于圈上的任意一点v有d(v)=r(r≥2),那么称G为圈-r-正则(n,n)-图.本文给出了C3-3-正则(n,n)-图(μ3n(3))能量的次小值与第三小值及对应的图.     

连通3-正则图的最大亏格与上可嵌入性

文章探讨了连通3-正则图的最大亏格与上可嵌入性,并得到了当γM(G)=「β(G)3■时连通3-正则图的结构特征.     

连通图的临界性

通过连通图的研究给出μ-临界 m-连通 m-正则图的一种构造方法.并给出关于μ-临界图的结论:G是4-连通(p,q)图,P≥8,如果存在线x=uv及SV(G)使G-x-S有两个支A,B,u∈A,v∈B,则当|A|≥3或|B|≥3时,G不是μ-临界图.     

含有k个悬挂点单圈图的原子键连通性指标

原子键连通性指标(ABC)为烷烃的稳定性和环烷烃的应变能力提供了一个较好的模型,其定义为ABC(G)=∑uv∈E(G)du+dv-2/d_ud_v~(1/2),其中du,dv分别表示图G中顶点u,v的度数.该文给出了n个顶点含有k个悬挂点单圈图的ABC指标的上界,并刻画出极图.     

关于图的Laplacian谱半径上界两个重要结果的新证明

设G为n阶简单连通图,V(G)为图G的顶点集,E(G)为图G的边集,λ_1(G)是Laplacian谱半径,d_u,m_u分别表示顶点u的度和平均2次度.给出λ_1(G)≤max(d_u+d_um_u)(X. D. Zhang. Linear Algebra Appl.,2004,376:207-213.)和λ_1(G)≤max(2d_u~2+2d_um_u)(J. S. Li, Y. L. Pan. Linear Algebra Appl.,2001,328:153-160.)这两个不等式的新证法.     

正则图的最大-团横贯数与减最大-团横贯数 (运筹学与控制论)

本文首先得到了阶数为n、团数为k的连通k-正则图的最大-团横贯数的上界n/k以及n阶连通无爪3-正则图的最大-团横贯数的下界n/4,并对达到这些界的极值图进行了刻画。然后对阶数为n、团数为ω(G)的任意图G的减最大-团横贯数给出了一个紧的下界1+ω(G)-n,同时对阶数为n、团数为k的连通k-正则图的减最大-团横贯数呈现了一个上界n/k,并刻画了达到这个上界的极值图。
     

二连通、无爪图是Hamilton图的一个充分条件

1985年,M.M.Matthews和D.P.Sumner证明了:若G是二连通无爪图,且δ(G)≥1/3(p-2),则有Hamilton圈。本文证明了:若G是二连通无爪图,且对手G的任意两个不相邻的顶点u和v,有d(u)+d(v)≥2/3(p-2),则G有Hamilton圈。     

图的λ4-最优性的邻域交条件

文章给出了图的λ4-最优性的邻域交条件.设图G是阶至少为34的λ4-连通图,若对G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且ξ4（G）≤3n（G）/2＋3,则G是λ4-最优的;若对于λ4-连通图G中任意一对不相邻顶点u,v,都有｜N（u）∩N（v）｜≥6且对图中每个三角形T至少存在一个顶点v∈V（T）...     

图的Laplacian矩阵谱半径

设G为n阶简单连通图,若L(G)为图G的度对角矩阵与邻接矩阵的差,则称L(G)为图G的Laplacian矩阵.结合非负矩阵谱理论,利用图的顶点度和平均二次度给出了图G的Laplacian矩阵的谱半径的新上界,同时给出了达到上界的极图.     

图的最大拉普拉斯特征值的上界

设G=(V,E)是n阶简单连通图,D(G)和A(G)分别表示图的度对角矩阵和邻接矩阵,L(G)=D(G)-A(G)则称为图G的拉普拉斯矩阵。利用图的顶点度和平均二次度结合非负矩阵谱理论给出了图的最大拉普拉斯特征值的新上界,同时给出了达到上界的极图,并且通过举例与已有的上界作了比较,说明在一定程度上优于已有结果。