一类无爪泛圈图

本文证明了如下结果:G 是 n(≥8)阶,2—连通无爪图,且对 G 的每一个生成子图 A、A~+,满足(a_1,a_2),则 G 为泛圈图(除圈外)。     

一类泛圈图

本文证明了如果G是2连通无爪图,G不是圈,n=|v(G)|>q,G的每个导出子图A都满足φ(a_1,a_2),且G中不存在W′作为其导出子图,则G是泛圈图。     

无爪图的Hamilton性

本文证明了如果G是2连通无爪图,G的每个导出子图A都满足(?)(a_1,a_2),且C中不含同构于D的导出子图,则G是Hamilton图.     

一类泛连通的无爪图

本文证明了:如果G是3连通的无爪图且G的每个导出子图A,A~(?)都满足ψ(a_1,a_2)则G是泛连通图(除了当u,v∈V(G),d(u,v)=1时,G中可能不存在(u,v)—k路,k∈(2,3,4)以外)     

K连通图的k分割多项式算法

图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法.     

k-连通半无爪图的Hamilton性质

半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k 1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。     

具有A-连通实现二部可图对的一个注记

设S=(a_1,…,a_m;b_1,…,b_n),其中a_1,…,a_m和b_1,…,b_n是2个非增的非负整数序列.如果存在一个简单二部图G=(X∪Y,E),使得a_1,…,a_m和b_1,…,b_n分别是X和Y中顶点的度,则称S=(a_1,…,a_m;b_1,…,b_n)为一个二部可图对.设A是一个阿贝尔群(以"0"为单位元的加法群),定义σ(A,m,n)是最小的正整数k使得每一个二部可图对S=(a_1,…,a_m;b_1,…,b_n)满足a_m,b_n≥2且σ(S)=a_1+…+a_m≥k时都有一个A-连通实现,确定了当|A|=4且m≥n≥3时,σ(A,m,n)的下界和当|A|=6且m≥n≥2时,σ(A,m,n)的下界.     

关于环的特征与交换性

本文主要讨论了含单位元的无零因子环内特征与交换的关系,得到如下主要结果: 定理1 设R是一个含单位元且无零因子的环,|R|≥p,且~a∈R,(a+e)~p=a~p+e,则charR=p。 定理2 设R是一个含单位元且无零因子的环,存在质数p>1,p≠CharR,使得~a∈R,(a+e)~p=a~p+e,则R为一个有限域。 定理3 假设1)R是一个特征为零的、含单位元、无零因子的环; 2)~x,y∈R,存在整数a_1,a_2,a_3,b_1,b_2,b_3使得:a_1xy~2+a_2yxy+a_3x~2y+b_1xyx+b_2yx~2+b_3y~2x=0则当R为可换时,(a_1+2b_3)(2a_1+a_2)(b_2+2a_3)(2b_1+b_2)≠0 反之,当此式左端任一因子不为零时,R为一个交换环。     

关于恰有一个圈的连通简单图的图序列

本文证明了只有一个圈的连通简单图的图序列的充要条件。设 G 是一个图,它有 n 个顶点 a_1,a_2,…,a.d(a_i)表示在 G 中与 a_i关联的边数。序列d(a_1),d(a_2),…,d(a(?))称为 G 的度序列。如果 G 为一简单图,那么它的度序列称为图序列。     

C.Thomassen猜想的证明

证明了若 G是 3连通无爪图 ,且 G的每个同构于 A的导出子图都满足 ( a1,a2 ) ,则 G是泛连通图 (除了 u,v∈ V( G) ,d( u,v) =1时 ,G中可能不存在 ( u,v)—k路外 )。由此立得C.Thomassen猜想 :每个 4连通线图均是 Hamilton图     

无爪图的泛连通性

证明了如果G是 3连通无爪图 ,且G的每个导出子图A、子图T都满足(a1,a2 ) ,则G是泛连通图 (当u、v∈V(G) ,d (u ,v) =1时 ;G中可能不存在 (u ,v) -k路 ,k =2 ,3,4除外 )。     

具有两个次限制点的第n棵次限制最小树

给定赋权在通图G=(V,E),指定P_1,P_2∈V,且P_1P_2在G中无边相连,再给定两对正整数a_1≤b_1,a_2≤b_2,若G的一棵支撑树T在P_i处的次|T(P_i)|满足a_1≤≤|T(P_i)≤b_i,则称为一棵次限制树。本文讨论了有序地寻找第n棵次限制最小树。把R.N.BurnS和C.E.Haff有关第n棵支撑树的结果推广到次限制树的情况。     

哈密尔顿连通图和邻域并条件（Ⅰ）

记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|：x,y∈V（G）mxt∈E（G）|,NC2=min{|N（x）∪N(y)|：x,y∈V(G),d(x,y)=2},1989年Faudree等证明了：若3连通n阶图G,NC≥(2n 1)／3,则G是哈密尔顿连通图。据此进一步研究NC2≥(2n 1)／3,而且研究到2连通图,得到下面结果：若2连通n阶图G,NC2≥(2n 1)／3,则G是哈密尔顿连通图或G=ψ。     

无爪图的泛连通性

证明了如果G是3连通无爪图,且G的每个导出子图A、子图T都满足φ（α、α2）,则G是泛连通图（当u、v∈V（G）,d(u,v)=1时;G中可能不存在（u,v）-k路,k=2,3,4除外）。     

距离无爪图的Hamilton性

距离无爪图类属于无爪图类。所谓距离无爪图是对图中的每一个顶点,其距离为的邻域的独立数均不超过3的图.F.BruceShephed已证明:若G是距离无爪图且G是2─连通的,则G有Hamilton路;若G是距离无爪图且G是3─连通的,则G有Hamilton圈.本文在此基础上,定义了一种新的禁用子图──网全爪,首先证明了2-连通的、无网的距离无爪图有Hamilton圈.又证明了2-连通的有网、无网全爪的距离无爪图有Hamilton圈.     

λ'-最优无三角图的最小边度充分条件

设S是连通图G的一个边割。若G-S不包含孤立点,则称S是G的一个限制边割。图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小度,则称图G是最优限制边连通的,简称λ'-最优的。设G是一个n阶的连通无三角图,且最小度δ(G)≥2.文章证明了,若最小边度ξ(G)≥(n/2-2 )(1+1/δ(G)-1),则G是λ'-最优的。并由此推出,若连通无三角图G的最小度δ(G)≥n/4+1,则G是λ'-最优的。最后给出例子说明这些结果给出的边界都是紧的。     

2-连通图的单圈子图

证明了如下结果:(1)一个2-连通图G的Θ-图是2(ρ-1)连通的;(2)如果一个2-连通图G有两个单圈支撑子图,且这两个单圈支撑子图分别含m和n个悬挂点(m相似文献   

2-连通无爪Hamilton图的一个充分条件

本文证明了:设G是n阶2-连通无爪图,△(G)≥n-4,则G是Hamilton图。     

2-连通图的单圈子圈

证明了如下结果:(1) 一个2-连通图的⊙-图是2(p-1)连通的; (2)如果一个2-连通图G有两个单圈支撑子图, 且这两个单圈支撑子图分别含m和n个悬挂点(m相似文献   

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

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称为与所给划分和正整数序列相对应的最优分级边连通图 .在给出顶点子集的边连通度概念的基础上 ,本文提出并讨论了有关最优分级边连通图的构造问题