极大3-限制性边连通图的若干充分条件

设G=（V,E）是一个连通图.如果λ3（G）=ξ3（G）,则G是λ3-最优或者极大3-限制性边连通的,其中ξ3（G）=min{|[X,Y]|:XV,|X|=3,G[X]连通}.G的逆度是指R（G）=∑_v∈V1/d（v）.本文主要研究R（G）与顶点数n,最小度δ及ξ3的关系,并由此得到一函数,用这一函数来限制R（G）,使G是λ3-最优的.     

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

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

二部图2-等周边连通度最优的充分条件

图G的k-等周边连通度是图的边连通度概念的推广。通过考虑无向图等周边连通度与不相邻顶点对邻域之间的关系,给出了二部图的2-等周边连通度最优的充分条件。     

图是极大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限制边连通的。     

超级等周边连通图的邻域条件

分析邻域结构对图的连通性的影响,利用图的顶点邻域与k阶子图之间的关系,给出了图是超级k阶等周边连通的一个充分条件。     

4等周边连通图的邻域条件

k等周边连通度是一个比边连通度更可靠的网络可靠性参数.连通图G的k等周边连通度定义为γ_k(G)=min{|[X,X]|:X■V(G),|X|≥k,|X|≥k},其中珡X=V(G)X.令βk(G)=min{|[X,X]|:X■V(G),|X|=k}.图G是γ_k-最优的如果γ_k(G)=βk(G).令G是一个阶至少为8的图.文章证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥3;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥7,那么G是γ4-最优的.     

5等周边连通图的邻域条件

文章研究了5等周边连通图的领域条件,若G是一个阶至少为10的连通图,对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足|N(u)∩N(v)|≥4;当u和v中至少有一个在三角形中时满足|N(u)∩N(v)|≥9,则G是γ_5-最优的.     

3—连通图具有Hamilton性质的充分条件

设Ｇ是ｎ阶简单３－连通图，δ是Ｇ的最小度，ｕｖ是Ｇ的两个不相邻顶点，ａ（ｕ，ｖ）是Ｇ中包含ｕ，ｖ的最大独立数，本利用图Ｇ的任意两个距离为２的顶点ｕ，ｖ的独立数ａ（ｕ，ｖ），给出了图具有Ｈａｍｉｌｔｏｎ性质的两个新的充分条件。     

极大等周边连通图的一个邻域条件

图的等周边连通度是图的边连通度概念的推广,通过考察图中顶点的κ阶子图之间的关系,给出一个图是极大κ阶等周边连通的一个充分条件:设κ≥2是一个整数,G是一个阶至少为2κ的图,如果对G中任意两个不相邻的顶点u和v,有|N(u)∩N(v)|≥2κ-2,进一步,如果这两个顶点中至少有一个是某三角形的顶点,有|N(u)∩(v)|≥2k-2,进一步,如果这两个顶占中至少有一个是某三角形的顶点,有|N(u)∩N(v)|≥2κ-1,那么图G是rk最优的.     

图中顶点子集的边连通度与最优分级边连通图的构造问题

G =(V ,E)是无向连通图 ,无环允许有重边 .S是V的至少包含两个顶点的子集 ,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数 .给定集合V和V的一个划分V =V1∪V2 ∪…∪Vr(|r|≥ 1,|V1|≥ 2 )以及正整数序列k1>k2 >… >kr≥ 2 .记Si=V1∪V2 ∪…∪Vi,1≤i≤r.构造一个连通图G =(V ,E)满足 :λG(Si)≥ki(1≤i≤r)且边数 |E|最小 .这种图G称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 ,本文提出并讨论了有关最优分级边连通图的构造问题     

3连通图生成树上的可去边

摘要：设G是3连通图，e是G中的一条边．若G—e是3连通图的一个剖分．则称e是3连通图G的可去边．否则，称e是G的不可去边．本文给出某些3连通图的生成树上可去边的分布情况及数目。     

图的集合边色数

给出了集合边色数的定义。运用结构图论的方法,给出了集合边色数的下界以及图与其顶点删除子图、边删除子图的集合边色数的关系。     

二部图λ3最优性的充分条件

本文给出了二部图λ3最优性的一些充分条件,它们在网络可靠性分析中有一定应用.     

λ_(3,q)-连通图的刻画(英文)

连通图G称为λ3,q-连通的如果存在边割S使得G-S有两个阶数分别至少为p和q的连通分支。给出一个图是λ3,q-连通的一些充分和必要条件。     

Almost every graph has a fixed edge

An edge e of a graph G is called a fixed edge if G-e+e′ G implies e′=e, and an isomorphic fixed edge if G-e+e′ G implies that there exists an automorphism of G-e, which maps the ends of e to the ends of e′. It is proved that almost every graph is with all its edges as fixed edges and isomorphic fixed edges, and it is conjectured that all graphs contain isomorphic fixed edges.     

一种有向图中求取强分图和单项分图的算法

给出一种通过有向图可达矩阵求取强分图和单向分图的方法,此方法回避了结点的次序问题.     

Hamilton图的充分条件

从1952年Dirac定理开始,Hamilton图的充分条件通常沿着边密度条件发展。Ore定理放宽了Dirac条件而且推广了控制图中顶点度的方法;进一步,Fan定理打开了一个全新的研究道路——尽管还是稠密性条件,但渗入某些局部化结构。1989年,Faudree等人提出了邻域并条件,近几年许多新结果不断涌现。文中,我们推广了上述结果,提出新的Hamilton图的充分条件。     

正则图的环边连通性和环连通性之间的关系

研究了一般3 正则连通图G的环边连通性和环连通性之间的关系,证明了G的环边连通度等于其环连通度。讨论了G的环连通度与环点连通度之间的关系,指出当G的顶点个数不少于其环连通度的6倍时,其环连通度等于其环点连通度。