无向广义De Bruijn图的m-限制边连通性

m-限制边割将连通图G分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图G的m-限制边通度,记作λm（G）.对于包含m-限制边割的连通图G,有λm（G）≤ξm（G）（m≤3）;如果λm（G）=ξm（G）,则称图G是极大m-限制边连通的.本文证明：当n≥7时,无向广义De Bruijn图UBG（2,n）是极大m-限制边连通的（m={2,3}）.     

多元De Bruijn图的限制边连通性

多元De Bruijn图UB(d, n)是De Bruijn网络的拓扑结构, 它具有高效网络应该具备的许多特性, 如短直径、小最大度和多节点. 本文研究无向多元De Bruijn图的的限制边连通性, 证明当n≥4时UB(d, n)是超级限制边连通的, 回答了张克民等人提出的问题.     

直径不超过4的树的零阶广义Randi指数

图G=(V,E)为简单连通图,dv表示顶点v的度。G的零阶广义Randi指数定义为Rα0(G)=∑v∈Vdvα,其中α为任意实数。本文研究直径不超过4的树关于零阶广义Randi指数的极图问题。     

超立方体网络的限制边连通性

m-限制边割将连通图分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图的m-限制边连通度.本文给出了n立方体的m-限制边连通度的表达式,由此推出：当m≤2（n/2）-1或m=2 k≤2n-1（k为任意正整数）时,超立方体Qn是极大m-限制边连通的.     

直径不超过4的树的零阶广义Randi(c)指数

图G=(V,E)为简单连通图,dv表示顶点v的度.G的零阶广义Randi(c)指数定义为R0α(G)=∑v∈Vdαv,其中α为任意实数.本文研究直径不超过4的树关于零阶广义Randi (c)指数的极图问题.     

苯系统的Randi指数

有机物分子的分子图G=(V,E)的Randi指数R(G)定义为∑uv∈E(1)/(d(u)d(v)),其中d(u)表示顶点u在G中的度.针对苯系统的规则性,利用平面图中边和面之间的关系,给定苯系统的六边形内面个数和最外层六边形内面个数,得出环状苯系统及凸的苯系统的Randi指数的一些计算公式.     

路的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.     

极小四阶限制边连通图

设G是有限简单无向图,k是正整数.使G-S每个分支的阶不小于k的边割S称为G的k阶限制边割.G的四阶限制边连通度λ4(G)是G的四阶限制边割之中最少的边数.若对于任意边e∈E(G),均有λ4(G-e)=λ4(G)-1,则称G是极小四阶限制边连通图.定义ξ4(G)=min {(e)(U):U(∪)V(G),G[U]是四阶连通导出子图},此处(e)(U)表示恰好有一个点在U上的边的数目.若λ4(G)=ξ4(G),则称G是λ4最优的.若每个5阶限制边割都孤立出G的一个5阶连通子图,则称G是超级5阶边连通的.笔者给出:极小四阶限制边连通图若不是λ4最优的,则是3正则,围长为5,任意边都关联5圈,且是超级5阶边连通的图.     

k阶限制边连通度最优的一个充分条件

设S是图G的一个边子集,若G-S不连通且每个分支的阶至少为k,则称S为G的一个k-限制边割.若G有k-限制连割,G的最小k-限制边割的边数称为G的k阶限制边连通度,记为λk(G).记ξk(G)=min{|[X,]|∶|X|=k,G|X|连通},若λk(G)=ξk(G),则称G是λK-最优的.证明了若对G中任意一对不相邻的顶点x,y都有d(x) d(y)≥n 2(k-2),且G不是G*k图,则G是λk-最优的.     

强乘积图的限制边连通度

文章研究了两连通图G1和G2的强乘积图G1G2的限制边连通度,给出了强乘积图的限制边连通度的一个上界,并确定一类特殊强乘积图的限制边连通度.     

苯系统的Randi指数

有机物分子的分子图G=(V,E)的Randi指数R(G)定义为∑uv∈E 1/(d(u)d(v))~(1/2),其中d(u)表示顶点u在G中的度.针对苯系统的规则性,利用平面图中边和面之间的关系,给定苯系统的六边形内面个数和最外层六边形内面个数,得出环状苯系统及凸的苯系统的Randi指数的一些计算公式.     

有向Kautz图的超级限制弧连通性

限制边连通度是比传统的边连通度更精确的网络可靠性指标.限制边连通度在有向图中有4个推广,分别对应有向图的4种限制弧连通度.有向Kautz图可以作为多处理机系统的基础拓扑,是一类重要网络.证明了有向Kautz图K(d,n)的4种限制弧连通度都为2d-2,并且确定了对应的最小限制弧割的结构特征.     

图是极大限制边连通的一个充分条件

设G是n阶简单无向连通图,G的限制边割是删除它以后G不连通,且留下的每个分支不含孤立点的边子集;限制边割的最小基数称为限制边连通度.记G的顶点x的度为d(x)。证明了若对超级连通图G中任意一对不相邻的顶点x和y都有d(x) (dy)n,则G是极大限制边边通的当且仅当G不同构一种特殊图G。     

优化正则图的限制边连通性的最小度条件

限制边割将连通图分离成不合孤立点的不连通图，如果最小限制边割只能分离孤立边，则称图G是超级限制边连通的．证明了如果k＞|G|/2 1，那么k正则连通图G是超级限制边连通的，k的下界在一定程度上是不可改进的．     

极大4限制边连通图的充分条件

设G=(V,E)是一个连通图。称一个边集合S?E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点。称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λk(G)。给出了图是极大4限制边连通的充分条件。     

图是极大3限制边联通的充分条件

设S是连通图G中的一个边子集。若G S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λκ(G)。定义ξκ(G)=min{|［X,X］|:|X|=k,G［X］连通},其中X=V(G)＼X。若λk (G)=ξk(G),则称G是极大k限制边连通的。设G是一个围长至少为5的λ3 连通图。本文证明了若G中不存在5个点u1,u2,v1,v2,v3使得d(ui,vj)≥3(i=1,2;j=1,2,3),则G是极大3限制边连通的。     

具有极大和次大广义Randi(c)-指数的极值化学树

通过对化学树定义一个新的分类,提出了当αO且n≥9时,具有极大和次大广义Randic-指数的极值化学树就在此分类中,并给出了详细证明.同时,给出了在上述条件下,极大和次大广义Randic-指数的差值.     

Bubble-Sort图的限制边连通度

一个图G的限制边连通度是使得G-F不连通且每个分支至少含有2个顶点的最小边子集F的基数.文章中,我们证明当n≥3时Bubble-sort图Bn的限制边连通度λ′(Bn)=2n-4.     

有向de Bruijn图的限制边连通度

证明了对有向de Bruijn图DB（d，n），当d≥3，n≥3或d=2,n≥3或≥3，n=时，它的限制边连通度λ^DB（d，n））=2d-2.