直径为3的图的最小特征值

设Y是一个图集合,若对于Y中的所有图中,图G的最小特征值可以达到最小,则称G是集合Y中最小特征值的极小图。本文刻画了直径为3的n阶连通图最小特征值及其极小图。     

直径图为11圈的7距离集研究

如果平面点集X中的任意两点确定的互异距离数为k,则称X为k距离集。用d(x,y)表示平面上互异两点x,y之间的距离,记X中的最大距离为直径D=D(X)。直径图DG(XD)是由X中所有直径构成的图,XD表示其顶点集。讨论了当X是一个7距离集时,直径图DG(XD)的构型。利用DG(XD)中最多包含一个圈,且只能为奇圈的特性,以及直径所具有的特殊性,证得当直径图为11圈时,其顶点集XD恰好为某正十一边形的顶点集。     

直径为3围长为6的二分图

讨论直径为d围长为g（＝2d）的二分图的结构,得到的结果为：若G是二分图,d（G）＝3,g（G）＝6,则G是图θ3^n,n≥2或（k,6）－图,k≥3,这里θ3^n（n≥2）是由n条内部不交的3－长路构成的图,（k,6）－图（k≥3）是具有度数k、围长6和顶点数no(k,6）的图。     

正则图的宽直径(英文)

宽度为m的图G的直径是最小整数d,使得G中任何两顶点之间至少存在m条其长度都不超过d的内点不交的路.对于任何满足[(2w+5)/3]≤m≤w的整数m,给出了n阶w正则w连通图的m宽直径的上界为[((n-2)(w-2))/((w-m+1)(3m-w-4))]+1.它能导出和改进某些已知结果.     

价是3围长为2的交换弱距离正则有向图

利用Cayley图和字典式积构造了一些新的弱距离正则有向图.进一步地,利用结合方案和商图的理论,对一类价为3围长是2的可交换的弱距离正则有向图的特征进行了刻画.     

给定距离数的有限点集直径图的研究

给定一平面点集X,若点集X确定k个互异距离,则称X为k距离集,其中最长距离称为直径D。XD表示所有直径端点构成的集合,m=m(X)=|XD|表示XD中的元素个数。DG(XD)表示X中的所有直径构成的图形。令g(k)表示确定k个距离的最大点集所含点的个数,目前对k≤6的g(k)取值有了确切的结果。研究了距离数k≥7的平面点集。首先,对m=|XD|=2k-1的k距离直径图DG(XD)中所有顶点的度值d(v)分析判断,得出d(v)≤2。在此基础上研究了7距离集的情形,证明当7距离集的直径图为DG(XD)=P10∪P2时,必有XD=R15-3。这是研究最大7距离集的基础。     

具有性质Г（X）≌3＊K3的距离正则图的一些结果

讨论了具有性质Г（X）≌3＊K3Г的距离正则图当d=r＋2，cr＋1=2时的一些情形，证明出当d=r＋2，cr＋1=2时，ar＋1≠5。     

关于4连通图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数.对任意k连通图,它的容错直径Dk,不超过宽直径dk.本文证明:当G是4连通图时,若D3=2,d4≤{D4 1,8D4-17};若D3≥3,d4≤max{3D2(3D4-1/2D2-13/2) 1,2D2D3(D4-2) D2-D22 1,3D2(D3-1)(D4-2)-3/2D2-3/2D22 1}并且证明对n(n≥3)连通图,当Dn=2时,2≤dn≤3.     

关于图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数。对任何k连通图，它的容错直径Dk不超过宽直径dk。论文证明d2≤max{(d1-1)(D2-1/2d1-1) 1,D2 1}；给出d1=2时d2=D2 1的一个充分必要条件：d2=3或d2=4且达到d2值的任何两顶点必相邻。     

关于Cayley图的直径

证明了有关Ｃａｙｌｅｙ图的直径的几个定理，并得到它们对有限群的问题的应用．     

图的ABC指标与直径

为了更好地研究拓扑指标在物理化学领域的良好性质,考虑基于度和基于距离的指标之间的关系问题,在直径这一作为距离的不变量的基础上,研究了图的ABC指标和直径的关系。根据相关引理,推导出了树和单圈图的ABC指标与直径的关系,得出了ABC指标和直径差值的紧的下界。     

完全分割图的最小直径定向

对于图G，记G的具有最小直径的定向图为G’，用K2[Kn,Km^-]表示由阶为n的团和阶为m的独立集构成的完全分割图．为了得到完全分割图K2[Kn，Km^-]的最小直径定向，首先给出Kn的一个定向Rn使得diam(Rn)=2，然后对Kn与Km^-之间的边也给出特殊的定向，并证明了下述结论：     

具有固定直径单圈图的Estrada指标

针对具有固定直径的奇单圈图类中Estrada指标的最大图,通过不断缩小它所在的范围,证明了Δ_n~d是具有固定直径的奇单圈图类中Estrada指标最大的唯一图.其中,Δ_n~d表示在三角形的一个顶点粘上n-d-2条悬挂边和一条长为[d/2]的路,另一个顶点粘上一条长为[d/2]-1的路所得到的图.     

关于2连通图的容错直径与宽直径的注记

在实时系统中,容错直径和宽直径是两个度量网络信息传输延迟和性能的重要参数.对于一般的图G,确定它的容错直径Dk困难很大,而确定它的宽直径dk却是个NPC问题,因此讨论它们之间的关系显得很重要.该文讨论了2连通图的容错直径与宽直径之间的一些性质,给出若G是直径为2的2连通图,则d2=D2+1的充要条件为存在两顶点u、v∈V(G),其中uv∈E(G),使得L(G)=L(G;u,v)=4或5.     

正则图Cartesian积的线图的秩

设G是一个顶点为n,度为r的正则图,那么它的边为m=1/2nr.G线图是顶点为m,度为（2r-2）,边为1/2nr（r-1）的正则图,本文研究两个正则图或强正则图的Cartesian积图的线图的秩,得到了许多结果,推广了G．J．Davis,G．S．Domke等人的结论．     

完全图强乘积的强半径和强直径

首先证明2个非平凡完全图强乘积是完全图且具有强定向性,然后确定了完全图强乘积的最小强半径和最小强直径的精确值,给出了最大强直径和最大强半径的范围.最后通过利用强乘积的结合性,将上述结论推广到多个完全图的强乘积.     

立方图中的路因子和圈因子

给定连通图集合Φ,对图G的生成子图F,如果F的每个分支都同构于集合Φ的一个元素,则F被称为G的Φ-因子.最近Kawarabayashi 等证明了:2-连通立方图有一个{Cn|n≥4}-因子和{pn|n≥6}-因子,其中Cn表示阶为n的圈,Pn表示阶为n的路.Kano等给出了每一个阶至少为8的立方偶图有{Cn|n≥6}-因子和{pn|n≥8}-因子的结论,并且提出猜想:阶至少为6的3-连通立方图有{Cn|n≥5}-因子和{pn|n≥7}-因子.现给出这个猜想的证明.     

Split完全图的最小直径定向

利用n 部完全图定向问题的结论,研究一类特殊图——split完全图的最小直径的定向问题,得到split完全图满足2 直径定向的条件及构作.