由对换树生成的凯莱图的3-额外连通度

给定一个图G和一个非负整数g,若图G中存在(边)点集,使得删除该集合后图G不连通并且每个连通分支的点数大于g,所有这样的(边)点集的最小基数,称为g-额外(边)连通度(记作κg(G)(λg(G)).本文将确定由对换树生成的凯莱图的3-额外(边)连通度(记作κ3(λ3).     

阶为奇且连通的双环网络的书式嵌入

嵌入阶为奇的双环网络.图G的书式嵌入包括把G的顶点放置到书脊上并且分配图!G的到书页上且保证每个书页上无相交的边.     

线图的邻域连通度

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

Euler环游图的连通度

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

广义笛卡尔积图的连通度

本文定义了图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的结果对循环图的连通度进行了讨论。     

超图的连通度（英文）

一个连通图或连通超图的连通度是使得图或者超图不连通所需要去掉的最小点数.显然,一个图(超图)的连通度κ不超过它的最小度δ.如果κ=δ,则图(超图)称为极大连通的.在本文中,我们给出了一致、线性、边传递(点传递)连通超图和连通无钻石超图的极大连通性问题.     

有向循环图的连通度

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

对换网络的可系性（英文）

G是一个图,k是一个正整数,u,v是G中任意两个不相同的点,u与v之间的一个k-container C(u,v)指的是从u到v的k条内部点不交的路的集合.并且C(u,v)被称作是k*-container,如果它包含G中所有的点.图G是k*连通的(或者说k生成连通的),如果对于G中任意两个不同的点u,v都存在u到v的一个k*-container.一个二部图G是k*可系的,如果对于来自不同部分的任意两个点u,v都存在u到v的一个k*-container.在这篇文章中我们证明了n阶对换网络TNn是(C2n)*可系的.     

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

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

小度数点传递图的连通度

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

增广立方体的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=(V,E)是一个无向有限简单图.记V=V(G)={v_1,v_2,…,v_n},我们构成一个n×n阶方阵A(G)=(a_(i j) )n×n:其中degv_i是顶点v_i在G中的度数。如果A(G)的特征值λ_1,λ_2,λ_n满足λ_1≤λ_2≤…λ_n,那么λ_1=0,而λ_2称为G的代数连通度(Algebrai Connectivitv),记为α(G)。它是由M.Fidler引进的关于函数α(G),有许多没有解决的问题,其中之一为:对于两个任意给定的正整数n和α,0≤α≤n—2,是否存在一个n阶图G,使得α(G)=α。本文给出上述问题的一个肯定的回答。为达此目的,只需对于给定的n和α,0≤α≤n—2,我们构造一个n阶图G,使得α(G)=α就行了。令     

邻接树图的连通度(英文)

G为重图其基圈数为ρ,本文证明G的邻接树图其连通度不大于ρ,近而指出此估界为最好可能的.最后还给出了这一结果的若干应用.     

广义Mycielskian图的连通度(英文)

Mycieski定义了一个图的运算即把一个图G变换为一个称为G的Mycielskian图的新图μ(G).广义Mycielskian图μm(G)(m≥0)是图的Mycielskian图的一个自然推广.本文证明对任意非平凡连通图G有κ(μm(G))=min{δ(G)+1,(m+1)κ(G)+1},而且对于m,i≥1,λ(μm(G))=λ(G)+i当且仅当δ(G)=λ(G)+i 1,其中κ(G),λ(G)和δ(G)分别为图G的连通度,边连通度和最小度.     

Harary图的外连通度(英文)

一个顶点集是一个Rg-点割,如果它将一个连通图分割成一些连通分支使得每个连通分支至少含有g个顶点.图G的g-外连通度(记作κg(G))是Rg-点割的最小基数.图G的通常的点连通度和上连通度分别相应的为κ0(G)和κ1(G).本文将分别证出第一类和第二类Harary图的κg和刻画它们的Rg-点原子部分.     

有向线图的等周弧连通度

一个有向图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的线图.     

连通、几乎局部连通、强K1,p-约束图的完全圈可扩

借助于新的连通性——几乎局部连通的定义．证明了连通、几乎局部连通、强K1，p--约束图,完全圈可扩,这一结果涵盖了膝延燕及尤海在拟无爪图上的相应结果。     

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

对任一个n阶单图G，用α（G）表示G的代数连通度，证明了对任一n阶单圈图G，有1≤α（G）＋α（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)是立方体的线图.