2连通无爪图的最长圈

本文所涉及的图都是有限无向简单图。设G是一个图,总用V(G)、E(G)、c(G)分别表示G的顶点集、边集、周长,而令p=|V(G)|。设U(?)(G),总用G[U]表示G中由U导出的子图。如果对于任意U(?)V(G),总有G[U](?)K_(1,3),则称G为无爪图。设λ=min{d(u)+d(v)|u,v∈V(G),uv(?)E(G)},δ=min{d(u)|u∈V(G)},其     

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

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

连通、局部连通、无爪图是点泛圈图

本文只讨论有限、无向、无环和多重边的简单图。V(G)、E(G)分别表示图G的顶点集和边集。如果S(?)V(G),用G[S]表示子集S在G中的导出子图。若u∈V(G),N(u)表示u点的邻域,即邻接于u点的全体顶点的集合。     

2-连通图的最长圈

设G=(V,E)是一简单、无向图,|V|=n,记N_i(u)={x∈V|d(x,u)=i},i≥1,其中d(x,u)表示点u到点x的距离。 设N_1(u)中点的度序列为d_0~1≥d_1~1≥…≥d_k~1。设N_2(u)中点的度序列为d_1~2≤…≤d_m~2。     

2-连通无爪图的泛连通性

一个图称作无爪图,如果它不含同构于K_(1,3)的导出子图。很重要的一类图——线图就是无爪的。目前已有的结果表明:相对于一般图而言,无爪图具有较好的性质。 关于无爪图的Hamilton性质,近年来     

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

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

关于1坚韧图的最长圈

设G是一个连通图,且t为实数,若对V(G)的每个子集S,t·ω(G—S)≤|S|,其中ω(G—S)是G—S的分支数,则称G是t坚韧的。 本文只讨论1坚韧图。设λ=min{d     

2连通k正则图的Hamilton性

B. Jackson(参见J. Comb. Theory(B),29(1980),27—46)证明了2连通k正则的图G=(V,E),当点数n≤3k时G有Hamilton圈;在“The improvcment of Jackson's result on Hamiltonian Cyclesin 2-connected regular graphs”一文中我们改进了Jackson的结果,证明了2连通的k正则图,当     

1坚韧图最长圈的新的充分条件

本文所涉及的图都是有限无向简单图。设G是一个图,用V(G),B和c(G)分别表示G的顶点集、边集和周长,d(u,v)表示u和v间的距离,且设p=|V(G)|。     

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

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

大次和的1-坚韧图中的最长圈

给定一个图G,以‘(G)表示G的周长,并记一(。卜Mi·{客“(一):‘一,ng一Li的结果:设G是”阶2一连通图,若厅(G))n李3.则G是哈密尔顿图. 推论2设G‘留;,若生(3,一23)2,》15奇数;1一2r|l!|||夕、||||书纷we A\是G的无关集a3(G)(3,一16),》16偶数;·3(。卜Mi·{客己(一卜!愈N(一,!”(14。:,。2,,3}是G的无关集则G是哈密尔顿图. 该推论改进了G〔罗1,若内(G)Fa夕bender的结果:设、。)一Mi·{{(知一14),(,)1一2李|训州日N(,‘:{,,,,2,。丹是G的无关集·、(‘卜Mi·{{立N(一)卜{一提使自N(。)铃价的无关集13),则G是哈密尔顿图. 推论3.设G…     

无爪图中圈的弦的最大数目

本文讨论无向简单图。设C=v_1v_2…v_mv_1是图G的一个圈,G的边v_iv_i称为C的一条弦,如果i(?)j±1(其中v_(m+1)=v_1)。我们用σ(C)表示圈C的弦数,σ(G)表示图G中弦的最大数目。     

连通图的平均距离

图G直径D(G),平均距离和不仅是图论中有意义的不变量,在分析通讯网络时也充当了重要的角色。1988年,Chung给出以下估计:     

临界h连通图中度较小的顶点

设G是临界h连通的非完全图,Hamidoune(Discrete Mathematics,32(1980),257—262)证明G中至少有2个度不大于3/2h-1的顶点,最近余景礼、马昱(华中工学院学报,1984,1)将结果改进为G中至少有δ(G)-h 2个度不大于3/2h-1的顶点,对已知的h与δ(G),上述的结果不是最好的,当h与δ(G)已知时,本文得到了G中度不大于3/2h-1的顶点数的最好下界,我们证明了如下定理。 定理1 设G是临界h连通的非完全图,则G中至少有2(δ(G)-h 1)个度不大于     

(k + 1)秩匀称线性无圈超图的计数公式

得到了（ｋ＋１）秩匀称线性无圈超图的计数显式,并应用Ｐｏｌｙａ计数定理,得到了（ｋ＋１）秩非标号匀称线性超树Ｈ和（ｋ＋１）秩非标号匀称线性无圈超图的生成函数。     

图的连通度与Hamilton连通性

一、引言 我们讨论的图均为简单图,K和α分别表示图的连通度和独立数。我们采用文献[1]的术语和符号,并记G_n~k={G丨G为n阶k-连通图},H_e={G丨G是Hamilton连通图},用P_H(u,v)表示从u到v的Hamilton路。图G中的路P称为控制路,如果G[P(G)\V(P)]均为孤立点.给出图G中的一条(x,y)-路P,总认为是从x到y定向,表示的反向。若u,v∈V(P),则uv表示P上沿从u到v的路。又u≠y,v≠x,则u~+和v~-分     

几类由PLD确定的连通图

给定简单图G=(V,E),其中V是顶点集,E是边集。若对V的两个顶点u,v,在G中存在含有i个顶点的一条(u,v)路,则称性质P_i(u,v)成立。令S_i(2≤i≤n)是G中有性质P_i(u,v)的无序顶点     

关于连通图幂中边不交1-因子

我们总假设G=(V,E)为p阶连通简单图,n为自然数.G的n次幂图G~n定义如下:V(G~n)=V(G),E(G~n)={uv:d_G(u,v)≤n,u,v∈V(G)},式中d_G(u,v)是u和v在G中的距离. 1984年,Nebesk(?)证明了:当P为偶数     

关于最大唯一圈图

P.Erd(o|¨)s于1975年提出了下列问题:设f(n)是有n个顶点的任何两个圈的长均不相等的图的最大可能的边数,试确定f(n)。十余年来,对这一问题的研究几乎没有进展。我们称Erd(o|¨)s问题中所描述的图为最大     

关于唯一泛圈的图

所谓唯一泛圈的图(简称UPC图)G是指一个简单图,对每一个l,3≤l≤v,它恰有一个长为l的圈。确定所有UPC图是一个尚未解决的问题(见文献[1],p247)。至今知道的UPC图只有七个,它们是K_3,C_5 e,G_8~((1)),G_8~((2)),G_(14)~((1)),G_(14)~((2))和G_(14)~((3))(见图1)。我们约定本文讨论的图都是恰含一个Hamilton圈的简单图,所用术语和记号凡未加定义的均采自文献[1]。