二分图中最小度条件与[a,b]-因子的存在性

设G=(X,Y;E)为二分图,其中|X|＝|Y|＝n.证明了:若n≥((a+b)2)/(b)-(a+b)/(b)且δ(G)≥(an)/(a+b),或δ(G)＞a+b+n-2bn+1,则G有[a,b]-因子.并且将说明,条件δ(G)≥(a)/(a+b)n为最好的;而当b＜n≤4b且bn+1为整数时,δ(G)＞a+b+n-2bn+1也是最好的.     

图与补图断裂度的关系

在这篇文章中,作者解决了图与补图断裂度关系的问题.主要结果:1、若n(≥4)阶图G与(?)都连通,则(1)-(n-5)≤B(G)_B(G)≤n-2:(2)对[-(n-5),n-2]中任一整数r,都存在G,使B(G)+B(?)=r.2、若n(≥5)阶图H与(?)都是Hamilton图,则(1)-(n-5)≤B(H)+B(?)≤0;(2)对[-(n-5),0]中任一整数r,都存在互补的Hamilton图H和(?)使B(H)+B(?)=r.     

线图上泛圈性的两个独立点的度和条件

设G是阶数为n 51的简单连通图,满足周长g(G)4,且2δ(G)(2n-9)/5。若G是哈密顿图,则其线图L(G)是泛圈图。     

关于边连通度与最小线度

本文主要证明了下面的结论: 设G是一个有n个顶点的简单田,若G中任何K(k≤4)个顶点v_1,…,v_k满足d(v_1)+d(v_2)+…+d(v_k)≥k/2(n-2)-1/2 则λ(G)=σ(G)。     

Reliability Analysis of the Cayley Graphs of Dihedral Groups

Cayley graphs have many good properties as models of communication networks.This study analyzes the reliability of the Cayley graph based on the dihedral graph.Graph theory and analyses show that almost all Cayley graphs of the dihedral graph D 2n are optimal super-λ.The number (G) i N of cutsets ofsize i,λ ≤i ≤λ' is given as Ni(G)=n((n-1)δ/i-δ).     

最小度与[a,b]-k-对等图

设G=(V(G),E(G))是一个n阶图,1≤an+(a+b)-2■bn-2k+1,则G是[a,b]-k-对等图。推广了已有的结果。     

完全对换图的广义3-连通度（英文）

令S■V(G)κ.G(S)表示图G中内部不交的S-树T1,T2,…,Tr的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(Ti)∩V(Tj)=S,E(Ti)∩E(Tj)=.定义κk(G)=min{κG(S)|S■V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.完全对换图在网络中是重要的一类Cayley图.该文证明了n-维完全对换图CTn的广义3-连通度是n(n-1)/2-1,也就是说,对于CTn的任意三个点,存在n(n-1)/2-1个连接它们的内部不交的树.     

无爪图的周长

设 G为 n阶 2连通无爪图,δ=min{d(x)|x∈V(G)},δ~*=min{max(d(x),d(y))|x.y∈V(G).d(x.y)=3},则(i)c(G)≥min{n.2δ~*+4};(ii)当 δ~*≥(1/2)(n-δ-2)时 G是哈密顿图。     

关于二部图圈的一个结果

设G=（X,Y;E）是连通二部图,｜X｜=n≥5,｜Y｜=n-δ,若NC2≥n-δ,则图G的周长C（G）≥2（n-δ）。进而G有控制圈。     

树的断裂度的紧上界

断裂度是图的哈密尔顿性和容错性的一个有效度量.对连通图G,它被定义为b（G）=max{w（G-S）-S：S是G的点断集},其中w（G-S）表示G-S的分支数.文章研究树的断裂度的上界,得到如下结论：设T是一棵阶为n（≥2）,最大度为Δ的树.若r（n-1/Δ）≠1,则b（T）≤n-2「n-1/Δd」;若r（n-1/Δ）=1,则b（T）≤n-2「n-1/Δ」＋1,其中r（n-1/Δ）和「n-1/Δ」分别表示n-1/Δ的余数和上整数.最后我们用例子说明这个上界是可达的.