临界2棱连通图的最大度及度大于4的点数

设G是临界2棱连通图,D是G中2度顶点集合,D_(≥2k-1)(G)={x:(x∈G)∧(d(x)≥2k-1)},D_(2k-1):2k(G)={x:(x∈G)∧(2k-1≤d(x)≤2k)},其中k是自然数。[a]表示不大于a的最大整数。我们得到如下结果:     

1坚韧图的Hamilton性

设G是一个图,且t是一个实数,若对每个,其中k(G—S)是G—S的分支数,则称G是t坚韧图(t-tough graph)。显然,1坚韧图是2连通的。用δ,κ,α分别表示G的最小度、连通度和独立数,利用以上记号,有如下定理: 定理1 设G是p阶1坚韧图,若δ≥     

紧李群上富里埃级数临界指标以下的(2K,δ)次Riesz求和

当δ>(1/2)(n-1),n=dim G,这时(2)式的性质我们已有专文作了较仔细的讨论,并用它证明了紧李群G上一致逼近及L_p逼近的Jackson型定理,这就产生了对δ≤(1/2)(n-1)时(2)式性质的讨论。而δ_0=(1/2)(n-1)称为临界指标。对此,有以下的定理,其中k=1时定理1和2中的若干结果,是已知的结果。     

块中圈含弦的最大数目及其极图刻划

设C为简单图G的圈,我们称导出子图G[C]的不在C上的边为C的弦。本文证得:设G是2-连通图且|V(G)|≥2n+1,n≥3。若G的最小度δ(G)≥n,则G含一个圈,其弦数至少为n(n-2)+1,除非G是K_(n,m)(m>n)或Petersen图。从而Gupta,     

边色数的分类问题及其有关性质

设图G为简单连通图,由Vizing定理可知△(G)≤x′(G)≤△(G)+1。其中,△(G)表示图G的最大顶点次,x′(G)是图G的边色数。若x′(x)=△(G),则称G为第一类图,并记为G∈C~1;若 x′(G)=△(G)+1,则称G为第二类图,记为G∈C~2。本文的目的在于讨论边色数的分类问题及其有关性     

2连通正则无爪图中的Hamilton圈

本文讨论的图都是无向的简单图。图G称为无爪的,如果G没有同构于K_(1,3)的顶点导出子图。 关于2连通正则图的Hamilton性,1980年B.Jackson证明了:若G是2连通、k正则图,且G的顶点数不大于3k,则G是     

图的度和、连通度和控制圈

令Ｇ是一个ｎ阶图.设Ｃ是Ｇ中的一个圈,如果Ｇ-Ｖ(Ｃ)是空图,那么称Ｃ是控制圈.令δ,κ和α分别表示图Ｇ的最小度、连通度和独立数.用σｋ表示Ｇ中任意ｋ个独立点的度和的最小值.Ｂａｕｅｒ等人[1]证明了:设Ｇ是ｎ阶2连通图.若σ3≥ｎ κ,则Ｇ是Ｈａｍｉｌｔｏｎ图.本文证明了:定理　设Ｇ是ｎ阶3连通图.若σ4≥ｎ 2κ,则Ｇ包含一个最长圈Ｃ,使得Ｃ是一个控制圈.界ｎ 2κ是最好可能的.我们能构造一类图,它们满足定理假设,但不是Ｈａｍｉｌｔｏｎ的.根据定理,我们有如下结论:推论1　设Ｇ是ｎ阶3连通图.若σ4≥ｎ 2κ并且δ≥α,则Ｇ是Ｈａｍｉ…     

k-连通无爪图中的Hamilton路和Hamilton-连通性

本文涉及的图都是无向简单图。而无爪图就是不存在顶点的导出子图同构于K_(1,3)的图。 1985年,Matthews等讨论了无爪图中的最长路和最长圈。证明了:设G是一个n阶无爪图,其最小次δ≥1/3(n-2)。若G     

极小n棱连通图的一个定理

D. R. Lick(J. Reine Angew. Math., 1972)首先证明:极小n棱连通图的最小度点数为n。W。Mader(Math。Ann。,1971)推广了上述结论,证明:极小n棱连通图至少有n 1个度n的点。本文推广了Mader的定理,证明了:     

求图的色多项式的一种新方法及其应用

设G是简单图,f(G,t)是它的色多项式,k是自然数,我们记 [t]_k=t(t—1)(t—2)…(t—k+1)。 定义1 若图G的生成子图H的每个分支都是完全图,则称H为G的理想子图。     

p阶临界2-边连通图的最大边数

设G=(V,E)是p阶简单无向图。 若G是2边连通的,设v∈V,若G-v不是2边连通的,则称点,是G的临界点。若G的每一点都是临界点,则称G是临界2边连通图     

(a,b,k)-临界图

本文所考虑的图皆指有限无向简单图。设G是一个图,具有顶点集合V(G)和边集合E(G)。文中未加说明的记号和定义参见文献[1]。设S(?)V(G),用G[S]表示G中由S导出的子图。用d_G(x)表示顶点x在G中的次数。设a和b是两个非负整数且a≤b。图G的一个[a,b]-因子是G的一个支撑子图H,使对任意的x∈V(H)有设。如果去掉图G的任意k个顶点所剩的图仍有[a,b]-因子,则称图G是(a,b,c)-临界图,或者说G是(a,b,k)-临界的。如果a=b=n,则简称(a,b,k)-临界图为(n,k)-临界图。如果n=1,则简称(n,k)-临界图为k-临界图。Plummer和Lovasz讨论了2-临界图的特征和性质。于青林给出了k-临界图的特征。刘桂真和于青林研究了(n,k)-临界图的特征。本文考虑a相似文献   

Hamilton图的一个充分条件

设G=G(V,E)为简单图。d(u)表G中顶点u的度,d(u,v)表顶点u与v的距离。ω(G)表G的分支个数。本文证明了下述定理。 定理 阶数n≥3的简单图G满足下述两条件:     

关于Benhocine、Clark等人的一个猜想

所讨论的图均指无向、有限的简单图。图G的生成闭迹或S-闭迹(S-circuit)是指一个闭迹使得它含有图G的所有的顶点。如果G中存在一条闭迹T使得G的每条边至少有一个顶点在T上,则称T是D-闭迹(Dominating circuit)。连通图G称为几乎无桥的如果它们的每一个桥至少关联一个次数为1     

局部n(弧)强连通有向图

G.Chartrand等在1974年提出了局部u连通的概念。本文将此概念推广到有向图(若有向图D中每个点的邻接点集的导出子图是n(弧)强连通的,则称D为局部n(弧)强连通的),然后给出了下面的定理。 定理1 任何弱连通的而且局部n弧强连通的有向图是(n+1)弧强连通的。 定理2 任何弱连通的而且局部n强连通的有向图是(n+1)强连通的。 定理2是G.Chartrand等的一个定理的推广,     

关于A.Ainouche和N.Christofides的一个猜想

一、引言 Ainouche和Christofides提出一个猜想:设a,b为2-连通图G=(V,E)的两个不相邻顶点,若,有,则G是Hamilton图当且仅当G+ab是Hamilton图。     

变系数高阶中立型微分方程的振动性

考虑变系数高阶中立型微分方程(NDDE)其中有界,且至少有一个q_i(t)最终大于某一任意小的正数。τ≥0,v_i≥0。m≥1,n≥1均为正整数。 定理1 设P(t)≥-1+δ,δ是一     

图的生成环及线图的Hamilton性

所讨论的图都是无向的、有限的简单图。图G的一个生成环(S-circuit)指的是一条通过图G所有顶点的闭迹。一个连通图称为几乎无桥图,如果G的任一桥至少关联一个度为1的顶点。1977年,F.T.Boesch、C.Suffel和R.Tindell提出了有生成环图的     

拟线性椭圆型方程广义解的最大值原理

设G是n维欧氏空间E~n中的有界连通区域,设α≥1 1/n为常数,设α(x)>0在G可测并且满足α(x)∈L_3(G),α~(-1)(x)∈L_t(G),     

Slater猜想的证明

图G称为k临界n连通的,如果对每一V′(?)V(G),其中|V′|≤k,有k(G-V′)=n-|V′|。这里k(G)表示G的连通度。一个k临界n连通图简称为(n,k)图。这一概念最早由Maurer与Slater在文献[1]中引进。Slater在文献[1]中提出如下猜想: 猜想A 当2k>n时,完全图K_(n+1)是唯一的(n,k)图。