有向线图的等周弧连通度

一个有向图D的k-阶等周弧连通度定义为：γ＋k （D）=min{｜（U,U^-）｜：U→∪V,｜U｜≥k,｜U^-｜≥k}.一个有向图满足γ^k＋ （D）=β^k＋ （D）时称为是γ^k＋-最优的,其中β^k＋ （D）=min{｜（U,U）｜：U→∪V,｜U｜=k,｜U^-｜≥k}.假设D是强连通d-正则的有向图且κ（D）≥3.本文我们证明了L（D）是γ2^＋-最优的,其中L（D）表示D的线图.     

有向循环图的连通度

本文给出了有向循环图连通度达到其最小度的一个充要条件.     

线图的邻域连通度

研究了图G的边邻域连通度λNB（G）和它的线图L（G）的点邻域连通度κNB（L（G））之间的关系,证明了AλB（G）≤κNB（G）．提出了一个新的概念：限制性边邻域连通度λrNB（G）,证明了κNB（L（G））≤λArNB（G）．最后,研究了上述两个不等式成为等式的充分条件．     

立方体的线图的限制性连通度(英文)

子集SE(G)称为是图G的4-限制性边割,如果G-S不连通且每个连通分支至少有4个点.图G中基数最小的4-限制性边割称为4-限制性边连通度,记为λ4(G).本文确定了λ4(Qn)=4n-8.类似的,子集FV(G)称为图G的Rg-限制性点割,如果G-F不连通且每个连通分支的最小度不小于g.基数最小的Rg-限制性点割称为图G的Rg-限制性点连通度,记为κg(G).本文确定了κ1(L(Qn))=3n-4,κ2(L(Qn))=4n-8,其中L(Qn)是立方体的线图.     

增广立方体的2-额外连通度

增广立方体AQ_n是超立方体Q_n的一个变体,它不仅保留了超立方体Q_n的几乎所有特征,还具有Q_n不具有的一些嵌入特性.本文利用图结构分析的方法讨论了增广立方体AQ_n的2-额外点(或边)连通度,证明了κ₂(AQ_n)=6n-18(n≥6),λ₂(AQ_n)=6n-7(n≥5)。该结论对衡量互联网络的可靠性和容错性有借鉴意义。     

广义笛卡尔积图的连通度

本文定义了图G_1、G_2的广义笛卡尔积图G=G_1∫G_2,并且证明了它们的连通度具有关系k(G)≥k(G_1)+k(G_2)。这一结果是对文[1]中关于G_1与G_2直积的结果的推广。此外,本文还讨论了G=G_1∫G_2的直径及Hamilton性。最后,利用G=G_1∫G_2的结果对循环图的连通度进行了讨论。     

Euler环游图的连通度

[1]中给出了Euler环游图E_u(G)的定义,并证明了E_u(G)具有边-Hamilton性。[2]中证明了E_u(G)是正则图。本文得到如下结果,对|V(E_u(G)|≥2,E_u(G)的连通度恰好等于其正则度数。     

N-G型的代数连通度的界

对任一个n阶单图G,用a(G)表示G的代数连通度,Gc表示它的补图.着重证明了2个图类的代数连通度的N-G型的界:a(G)+a(Gc)≥1.     

超连通图的充分条件

Let G be a connected graph. The connectivity κ(G) of a connected graph G is the least positive integer k such that there is F⊂V,|F|=k, and G-F is disconnected or is a trivial graph. If every minimum vertex cut isolates a vertex of G, a graph G is super connected or super-κ. Define the inverse degree of a graph G with no isolated vertices as R(G)=1/(d(v)). In this paper, we show that let G be a connected graph with order n and minimum degree δ, if R(G)<1+2/(δ+1)+(n-2δ-1)/((n-1)(n-3)), then G is super-κ.     

小度数点传递图的连通度

众所周知,ｋ（ｋ≤４）正则连通点传递图的连通度达到了它的正则度ｋ,本文证明了除Ｃｎ◎Ｋ２（ｎ≥４）外,每个５正则连通点传递图的连通度都是５,其中Ｃｎ◎Ｋ２是ｎ长圈与完全图Ｋ２的字典积。     

有向图及乘积图的路由数

s-图的路由数源自于网格上行走的机器人的坐标规则问题．Onn和Sperner指出该问题是NP-完全的并进而提出这样一个问题：平面图上的路由数是否一定存在仅由半径为参数构成的界？本文引入有向s-图的路由数这一概念并证明该数等于其周长．这一结果表明无向s-图的路由数等于该图所有定向图的最小周长，同时也对上面的问题给出了一个反例．做为一个应用．我们证明乘积图的路由数等于其半径．     

传递图中的限制性边连通度

设G=(V，E)是一个连通图，S包含于E是一个边子集，如果G—S不再连通，且G—S的每一个连通分支都至少含有r个点，则称S为一个r-限制性边割．最小r-限制性边割中所含的边数为G的r-限制性边连通度，记作λ(G)．如果对所有的i=1，…，r，λ(G)都达到其最大可能值，则称G为λ-最优图．王铭和李乔证明了：若G是一个d-正则的点传递图，d≥4，围长g≥5，或者G是一个d-正则的边传递图，d≥4，围长g≥4，则G是λ（g-1)-最优图．本文推广了这一结果，证明了：在同样的条件下，G是λg-最优图．     

六角系统中同谱图的搜索结果

论证六角系统中是否存在同谱图，如果存在，找出这些同谱图，具有重要理论与应用价值，作者用不同于「１」的方法搜索出了同谱图。     

线团图的一些性质

B.Hedman在文[1]中介绍了构造线团图的一个算法.本文用这一算法得到了线团图的一些性质.它们涉及到图的连通度、直径和色数.     

对称群上Cayley图的连通性

本文研究限制性边连通度的λ′-原子．运用所得结果可以证明Cayley图C(Sn,S)是最优超-λ的．这里Sn是n次对称群,S是若干由奇置换构成的共轭类的并，另外，我们还证明了C(Sn，S)是Vosperian的．除非它是完全二部图．