给定围长的图的超三限制性连通度的充分条件

图G是一个连通图.称X为三限制性割,如果G-X的每个连通分支至少有三个点.三限制性连通度k3(G)是三限制性割的最小基数,更进一步,如果图G的围长为4,去掉最小的三限制性割孤立出一条二长路,则称它是超三限制性连通的.本文给定了图是超三限制性连通的直径围长充分条件,还研究了超三限制性边连通图.     

立方体的线图的限制性连通度(英文)

子集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)是立方体的线图.     

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

设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是超-κ的.     

关于连通图最长圈的一个结果

设C是k-连通图G（2≤k≤6）的一个最长圈.H是G-C的一个分支.[5]中证明,若L（H）≥k-2,则｜C｜≥kδ-k（k-2）,这里L（H）表示H中最长路的长度,δ表示G的最小度.本文在H满足特定的条件时,对于k∈{3,4,5}改进了上述｜C｜的度下界.     

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

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

Harary图的外连通度(英文)

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

关于临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——临界h棱连通图的性质和最大临界3棱连通图类的刻划

设λ(G)表示G的棱连通度,图G称为临界h棱连通的,如果λ(G)=h而且对任何x∈V(G),λ(G-x)≤h-1,具有最大棱数的临界h棱连通图称为最大临界h棱连通图.本文首先证明对h≥3的临界h棱连通图的若干性质,然后证明最大临界3棱连通图的每个顶点都与3度点相邻,并由此给出了此类图的结构刻划和最大棱数.     

变换图G++-的超力连通性

对于图G,一般有λ(G)≤δ(G).如果λ(G)=δ(G),称图G是较大边连通的.如果G的每一个最小边割只能分离G的一个孤立点.称图G是超边连通的.本文证明了几乎所有的有限图G,其变换图G -都是超边连通的.     

平衡半传递有向图的弧连通性

有向图D=（V, E）被称为是极大弧连通的,如果λ（D）=δ（D）。此外,有向图D被称为是超弧连通的,如果每个最小的弧割都是其某个点的入弧集或者出弧集。以X1和X2为两部的一个有向二部图是半传递的,如果自同构群Aut（D）分别传递的作用在X1和X2上。在这篇论文中,证明了强连通的半传递有向图是极大弧连通的。还证明了除了少部分例外,连通半传递平衡有向图是超弧连通的。     

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

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

对称群上Cayley图的Hamilton性（Ⅱ）

对于每一个ｎ（≥３）阶连通简单图，都可定义一个相应的对称群上的Ｃａｙｌｅｙ图．本文继续文献［１］证明了每一个连通简单图对应的Ｃａｙｌｅｙ图都是一个Ｈａｍｉｌｔｏｎ图，从而在这方面的问题得到了圆满的解决．     

3-连通P3-支配图的Hamilton性

引进了P3-支配图并对BROERSMA HJ和VUMAR E提出的作为半无爪图的一个超类,研究了这类图的一些性质.得到:若G是n阶3-连通P3-支配图,则当n≤5δ-4时,G是Hamilton图.     

对称群上Cayley图的Hamilton性（Ⅰ）

对于每一个ｎ（≥３）阶连通简单图．都可定义一个相应的对称群上的Ｃａｙｌｅｙ图．本文为《对称群上Ｃａｙｌｅｙ图的Ｈａｍｉｌｔｏｎ性（Ⅱ）》做了准备工作，同时证明了若树Ｔ对应的Ｃａｙｌｅｙ图是一个Ｈａｍｉｌｔｏｎ图．则Ｔ任添一树叶对应的Ｃａｙｌｅｙ图也是一个Ｈａｍｉｌｔｏｎ图．     

路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

关于G.L.Chia和C.K.Lim的一个问题

G.L.Chia 和 C.K.Lim 提出下列问题:“设 G 是完全超紧图.若 G 是自补完全超紧图,那么 G 是自补图吗?”本文回答了这个问题.     

单位区间图的边泛圈性

本文证明了顶点数至少为４的单位区间图是边泛圈图当且仅当它是３连通的。     

单圈图和双圈图的连续边着色

设G是简单图,用颜色1,2,3,…对G的边正常着色,如果在每一顶点表现的颜色构成一个连续的整数集合,那么就称这个着色是连续的.图G的亏度def(G)是粘在G上使得它可连续着色的悬挂边的最小数目.在本文中,我们完全确定了单圈图和双圈图的亏度.     

具有较小秩的带号图的刻画

带号图是每条边带有符号（正或负）的简单图.探讨了带号图的秩,刻画了秩为2与3的带号图,以及秩为4的带号二部图.     

单圈图最小特征值的Sharp下界

设G是一个具有n个顶点的简单图，λn(G)为图G的最小特征值，而单圈图就是其边数等于点数的连通图，本文给出了单圈图最小特征值的一个Sharp下界，并同时给出达到这个下界的极图。     

2-连通P3-支配图的可迹性

令G是n阶2-连通P3-支配图,本文证明了如果G满足2N C≥n-2,则G是可迹的.