超级边连通r一致超图的充分条件

若一个连通图的任一最小边割一定是某个顶点的关联边集,那么称该图是超级边连通的.对超级边连通图的研究,不仅有理论意义,而且在网络可靠性的分析中也有广泛应用.超图是图的一个自然推广.论文将超级边连通性的概念推广到超图,给出超级边连通一致超图的最小度条件,并用例子说明所给的条件是紧的.所得结果是无向图相关结果的推广.     

关于广义棱连通度的一个注记

将广义棱α（G）的定义推广到m＋1个同构图的情形,定义了图a^m（G）,得到广义棱矿（G）的点连通度和边连通度的几个性质．     

图的三阶边连通度的优化问题

设F是图G的一个边子集,若G-F不连通且它的每个连通分支至少有3个顶点, 则称F为G的一个三阶边割. 若G有三阶边割, 把G的最小的三阶边割所含有的边数叫作G的三阶边连通度,记作λ₃(G). 研究λ₃(G)的优化问题, 首先引进λ₃(G)的极大性和超级性这两个组合优化概念,然后分别给出λ₃(G)实现极大性和超级性的Ore型充分条件. 这些概念和结果在网络可靠性分析中有重要应用.     

Star网络的限制边连通度

Star网络被认为是超立方体网络的良好替代.而限制边连通度作为传统边连通度的推广是互连网络容错性的一个重要度量.通过考察一些Star网络的拓扑性质,证明了当n≥4时,它的限制边连通度是2n-4.     

直径为2的图的超级边连通性质

Ｍ．Ａ．Ｆｉｏｌ在１９９２年给出了直径为２的无向简单图是超级边连通的三个充分条件（Ｆ１）、（Ｆ２）和（Ｆ３）．本文证明了：（１）条件（Ｆ１）也是必要条件,从而得到直径为２的图是超级边连通图的特征刻画;（２）（Ｆ３）（Ｆ２）（Ｆ１）,但（Ｆ１）／（Ｆ２）／（Ｆ３）;（３）条件（Ｆ３）可进一步保证图是最优超级边连通的,但（Ｆ２）不能．这里的最优超级边连通的概念是通过限制性边连通度自然地定义的．最后提出两个有关的待解决的问题．     

路的k阶幂图的连通性研究

设G是连通图,G的k阶幂图G^k是一个与G具有相同顶点集的图,G^k中的两个顶点相邻当且仅当这两个顶点在G中的距离不大于k.本文研究了路的幂图P_n^k的点连通度κ(P_n^k)、边连通度λ(P_n^k)和限制边连通度λ₂(P_n^k).得到：当n>k时,κ(P_n^k)=λ(P_n^k)=k;关于限制边连通度：当2≤n≤k+1时λ₂(P_n^k)=2n-4,当n>k+1时,λ₂(P_n^k)=2k-1.     

完全二部图的λ4-最优性

分析了完全二部图Kr,s的λ4-最优性.     

广义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的连通度,边连通度和最小度.     

k-连通图的无符号Laplace谱半径

设G是一简单图,K(G)是图G的无符号Laplace矩阵,K(G)的谱称为G的无符号Laplace谱。本文描述一类给定点连通度或边连通度图的无符号Laplace谱半径。     

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

本文给出了图的λ4-最优性的邻域交条件:设图G是阶数大于等于11的λ4-连通图,对G的任意一对不相邻顶点u,v,若u,v均不在三角形中,有|N(u)∩N(v)|≥5,若u或v在三角形中,有|N(u)∩N(v)|≥7,则G是λ4-最优的;若G中任意一对不相邻顶点u,v满足|N(u)∩N(v)|≥5,任意一条边xy满足|N(x)∩N(y)|≤2,则G也是λ4-最优的.这些结果在网络可靠性分析中有一定应用.