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

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

Euler环游图的连通度

[1]中给出了Euler环游图E_u(G)的定义,并证明了E_u(G)具有边-Hamilton性。[2]中证明了E_u(G)是正则图。本文得到如下结果,对|V(E_u(G)|≥2,E_u(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.     

n—补树图及其性质

补数图是为了研究特殊的R L电路网络结构而引入的,它的定义如下:设G是连通图,若存在两棵生成树T_1和T_2,且满足G=T_1UT_2,T_1 ∩T_2=φ,则称G是补树图,或称G具有补树结构。对这种图的性质,已有人作了一些讨论。本文的目的在于_2将补树图的概念推广到n-补树图,并讨论它的一系列性质。这样,[1]中定义的补树图即为本文定义的n-补树图的一个特例-2-补树图,而[2]中所论的补树图的一些性质也成为本文讨论的n-补树图的性质的直接推论。     

Cm□Cn的支撑树的一些性质

积图G1□G2是一个以笛卡儿积V(G1)×V(Gt)作为其点集．其中点(u,v)点(x,y)相邻当且仅当u=v且v与y在G2中相邻,或者v=y且u与z在G2相邻．证明了对图Cm□Cn的任意支撑树T,其中m和n不全为偶数,总存在一条Cm□CnT之外的边,添加到T上形成一个长度至少为m n-1的圈．这解决了陈(Dis-creteMathemstics 287(2004)11-15)给出的一个公开问题．     

一致最可靠完全多部图

对于一个连通图G,假设边是可靠的而点以P的概率相互独立地发生故障.图G不连通的概率是一个多项式P(G,p).记作Ω(n,m)是有n个点,m条边的连通图的集合.如果对于任意的网H ∈Ω(n,m)和任意实数p ∈[0,1],P(G,p)≤P(H,p)成立,则称G是Ω(n,m)中的一致最可靠图.本文证明了完全k部图K(b,(b+1)k-3,(b+2)2)是它所在的类中的一致最可靠图.另外,还证明了对任意的h≥2,K(bh,(b+1)k-h-1,(b+2)1)不是其所属类中的一致最可靠图.     

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

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

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

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

关于图的生成连通性的综述（英文）

图G的生成连通度为最大的正整数k使得G的任意两个顶点之间存在i (1≤i≤k)条内部不交的路,并且这些路的并生成G.文章不仅涵盖了有关图的生成连通度的最新研究进展,还包含了图的生成连通度相关的超生成连通性、生成可系性、超生成可系性等问题的最新结果.除此之外,还讨论了一些值得进一步研究的问题.     

传递图中的限制性边连通度

设G=(V，E)是一个连通图，S包含于E是一个边子集，如果G—S不再连通，且G—S的每一个连通分支都至少含有r个点，则称S为一个r-限制性边割．最小r-限制性边割中所含的边数为G的r-限制性边连通度，记作λ(G)．如果对所有的i=1，…，r，λ(G)都达到其最大可能值，则称G为λ-最优图．王铭和李乔证明了：若G是一个d-正则的点传递图，d≥4，围长g≥5，或者G是一个d-正则的边传递图，d≥4，围长g≥4，则G是λ（g-1)-最优图．本文推广了这一结果，证明了：在同样的条件下，G是λg-最优图．     

次模函数近似算法求最小颜色生成树

给定图G并对其进行边着色,G的最小颜色生成树（MCST）问题是指,找出G的一棵生成树,使得其边集所着颜色数最少.最小颜色生成数问题MCST已被证明是NP-、APX-完备的,从而此问题没有近似比为常数的近似算法.本文中,我们利用次模函数理论（贪婪算法的思想）给出最小颜色生成树问题的一个近似算法,且此算法的近似比为最好结果.     

列表双临界图（英文）

G是k-可着色的连通图,如果对于G中的所有边uv,都有G-u-v是(k-2)-可着色的,则称图G是双临界图.由Erdo?s和Lova′sz提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图,如果G中包含多对不相邻的边,并且对于任意一对不相邻的边e1,e2,都有χ(G-e1-e2)=χ(G)-2,其中χ(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中,对于任意的两个点u,v∈V(G),如果ch(G-u-v)=ch(G)-2,则图G是完全图,其中ch(G)表示G的选择数,还证明了完全图是唯一的列表双临界图.     

一类(0,1)矩阵变换图的Hamilton性

设G(R,S)表示m×n阶(0,1)矩阵类(R,S)的变换图.Brualdi提出问题:“G(R,S)有Hamilton圈吗?”当min{m,n}=2时,文献[3]中证明了此变换图是Hamilton连通的,并且是泛圈的(除K_1,K_2外),从而给该问题一个肯定的答案,当min{m,n}=3时,本文进一步地证明了此变换图是边Hamilton的(除K_1,K_2外),从而也给出该问题一个肯定的答案。     

一类正则图的边坚韧度

证明了一类r-正则r=x1(G)连通非完全图G的边坚韧度近似等于r/2(1 1/Iv(g)I-2)并且提供了估计一些特殊图类的笛卡儿积和Kroneeker积的边坚韧度的公式.     

广义笛卡尔积图的连通度

本文定义了图G_1、G_2的广义笛卡尔积图G=G_1∫G_2,并且证明了它们的连通度具有关系k(G)≥k(G_1)+k(G_2)。这一结果是对文[1]中关于G_1与G_2直积的结果的推广。此外,本文还讨论了G=G_1∫G_2的直径及Hamilton性。最后,利用G=G_1∫G_2的结果对循环图的连通度进行了讨论。     

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

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

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

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

一些特殊图类乘积的离散度

连通图的离散度是用s(G)来表示的,s(G)=max{ω(G-S)-|S|:ω(G-S)>1,SV(G)}.给出了两个完全图乘积的和一个完全图与路的乘积的离散度.还给出了两个完全图乘积的坚韧度.     

关于四边形连通无爪图的注

文献【1】中,证明了没有1度点的每个四边形连通无爪图G如不包含同构于G1或G2（见图1）的导出子图日使得H中每个4度点x的N1（X,G）是不连通的,那么它是哈密尔顿的．然而,在文献【2】中,命题2．5和定理2．6的叙述和证明中存在一些问题．在本文中,给出了它们的正确表述以及改进了的证明．     

关于3-连通图最长圈的注

设C是3-连通图G的一个最长圈,H是G-V(C)的一个分支满足|H|≥3.文献[4]在给H附加一些条件后,证明|C|≥2d(u) 2d(v)-5,并且不等式严格成立除非G属于某些例外图类,这里u,v是G中两个不相邻的顶点.本文给出了上述例外图类的精确刻划.