超连通图的充分条件（英文）

设G是一个连通图.图的连通度κ(G)存在一个最小正整数k,使得FV,|F|=k且G-F不连通或是一个平凡图.如果每一个最小点割都孤立G的一个点,则图G是超连通的或超-κ的.定义没有孤立点的图G的逆度为R(G)=∑v∈V1/d(v).得到:设n阶连通图G,最小度为δ,若R(G)1+2/(δ+1)+(n-2δ-1)/((n-1)(n-3)),则G是超-κ的.     

圈的笛卡积的圈点连通度（英文）

设G是一个点集为V(G),边集为E(G)的图.对于图G的点子集S,如果G-S不连通并且至少两个连通分支包含圈,则称S为一个圈点割.如果一个图有圈点割,称该图为圈可分离的.一个圈点可分离图G的最小圈点割的阶数被称为圈点连通度,记作κ_c(G).文章证明了κ_c(C_3□C_(n1)□Cn_2□···□C_(nk))=6k和κ_c(C_(n1)□C_(n2)□···C_(nk))=8k-8,其中对于i=1,2,···,k,Cni是一个长度大于等于4的圈.     

哈林图的偶匹配可扩性

称图 G 的匹配 M 是偶匹配,如果 M 中的边关联的点集在 G 中的导出子图是偶图,即 G[V(M)] 是偶图. 称图 G 是偶匹配可扩的,如果 G 的每一个偶匹配 M 都包含在 G 的一个完美匹配中. 本文的主要结果是:哈林图 H=(T∪C)是偶匹配可扩的当且仅当它的特征树 T 同构于 K1,3、K1,5 或者 K1,7.     

二面体群的双凯莱图的匹配可扩性（英文）

令G为有限群,S为G的非空有限子集,G关于S的双凯莱图BC(G,S)是一个二部图,其顶点集是G×{0,1},边集是{(g,0)(sg,1)|g∈G,s∈S}.若有完美匹配的连通图Γ至少有2n+2个顶点,且每一个大小为n的匹配都可以扩充为一个完美匹配,则称此完美匹配的连通图Γ是n-可扩的,并对二面体群的双凯莱的2-可扩性进行了刻画.     

二面体群的双凯莱图的匹配可扩性

令G为有限群,S为G的非空有限子集，G关于S的双凯莱图BC(G,S)是一个二部图,其顶点集是G×{0,1},边集是{(g,0)(sg,1)|g∈G,s∈S}.若有完美匹配的连通图Γ至少有2n+2个顶点,且每一个大小为n的匹配都可以扩充为一个完美匹配，则称此完美匹配的连通图Γ是n 可扩的,并对二面体群的双凯莱的2 可扩性进行了刻画.     

2k-点可删的导出匹配可扩图

设G是一个简单图．称G是2k-点可删的导出匹配可扩图,如果对于V（G）的任一满足│S│=2k的子集S,G—S是导出匹配可扩的．给出了2k-点可删的导出匹配可扩图的两个充分条件,证明了这两个条件都是最好可能的．     

关于图的边着色的一个猜想

若G是简单图,v(G)是偶数,χ'(G)=?(G)+1,则存在点v∈V(G),使χ'(G-v)=χ'(G)=?(G)+1.本文对此进行了研究,当图G满足以下条件之一时:(1)设G是含有割边的连通图,χ'(G)=?(G)+1;(2)设G是连通图,κ'(G)=2,G中最多除两个2度顶点外,其它顶点的度数均为k(k2),v(G)=2n+2,χ'(G)=?(G)+1;(3)设图G是k正则图,v(G)=2n+2,χ'(G)=?(G)+1;(4)设图G是有2n+2个顶点的连通图,且除点v的度小于k外,其它顶点的度都等于k,χ'(G)=?(G)+1;(5)设图G是有2n+2个顶点的连通图,且除点u,v,d(v)d(u)k外,其它顶点的度都等于k,χ'(G)=?(G)+1;此猜想也是成立的.     

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

超图的连通度（英文）

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

双广义Petersen图的可靠性分析（英文）

设G是连通图,图G的超连通度(超边连通度)是指从图G中删除最小数目的点(边)使得G不连通,且在G的每个分支中不存在孤立点.周进鑫和冯衍全(2012)首次提出了双广义Petersen图的概念,文章证明了双广义Petersen图DP[n,k]是超连通和超边连通的,以及当n?{2k,3}时,κ_1(DP[n,k])=λ_1(DP[n,k])=4.