Hamilton图的一个充分条件

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

K_(1,3)-free图中的圈

本文说的是简单图。 设G是任一个n阶的图。如果G中有长为n的圈,则G是哈密顿图。如果对每个k,3≤k≤n,G含有长为k的圈,则说G是泛圈图。如果对G的每个顶点v,图G中都有长为k的圈经过顶点v,则说G是点k圈图。如果对每个k,3≤k≤n,G都是点k圈图,则说G是点泛圈图。     

正则竞赛图有两个弧不重的Hamilton回路

Kelly提出:正则竞赛图T是否能分解为1/2(|T|-1)个弧不重的Hamilton回路(|T|表示T的顶点个数).此猜想是图论中至今未解决的难题之一.近年来,国外关于Kelly猜想的工作有:Alspach证明了9个顶点以下的     

关于路图P_3(G)的Hamilton性的两个结果

“路图”是线图概念的发展.给定一个图G及自然数k≥2,路图P_k(G)的顶点是G中k个顶点的路P_k;两条路P_k在路图中是相邻的,如果它们的并是P_(k+1)或C_k.为     

关于Chowla的一个猜想的注记

在1978年的国际数学家大会上,R.Ap(?)ry给出了ζ(3)sum from n=1 to ∞1/n~3是无理数的证明.为此,R.Ap(?)ry 定义了一个迭代数列a_n:a_n=1,a_1=5,n~3a_n-(34n~3-51n~2+27n-5)a(n-1)+(n-1)~3a_n-2=0,它满足a_n=sum k=0 to n (n/k)~2 (n+k/k)~2.这以后,很多人对Ap(?)ry 数a_n 进行了研究,并提出了一些猜想.姚琦证明了Chowla提出的关于a_n 的一个猜想:对一切素数p≥5,有a_p=5(modp~3).本文则证明了定理对于正整数l 及素数p≥5,有     

弧哈密顿竞赛图的一个性质

设T是有p个顶点的一个竞赛图。若T的每一条弧都在一个长度为k的回路上,则称T为弧k回路的。若T是弧p回路的,也称T为弧哈密顿的。     

关于2树的1因子定理

Bineke等人研究了2树的特征。本文给出了一个2树有1因子的充分必要条件。有3个顶点的2树是一个三角形。当n≥3时,有n 1个顶点的2树T是从有n个顶点的2树T′增加一个新的顶点和一个含这个顶点的三角形     

一类竞赛图

Müller和Pelant已经证明,如果T是n阶非传递竞赛图,n≥5,则T的所有n-2阶子竞赛图具有相同的得分序列的充要条件是,T为二重正则的。在本文中,我们确定所有n-1阶子竞赛图具有相同的得分序列     

(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相似文献   

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

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

关于紧带边流形的嵌入和分类

Haefliger和Hirsch在文献[1]中的定理3.1指出:设M是k连通n维闭流形,M_0=M—D~n,则有 (a) 如v≥2n-k-1,则M_0到R~v的任内浸均正则同伦于一个嵌入; (b) 如v≥2n-k,则M_0到R~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)的无序顶点     

定向图中的路和回路

一个没有环的,任意两个顶点之间最多只存在一条弧的有向图,称作为定向图。定向图D=(V,A),其中V是D中的顶点集合,A是D中的弧集合。令D中各顶点的出度和入度不小于k.Jackson证明了D中存在一条长度至少为2k的通路。在本文中,将给出一个更好的结果。     

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

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

关于连通图幂中边不交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为偶数     

关于边不交的Hamiltoh圈

本文所讨论的图均为无向的简单图。用δ(G)表示图G的最小度。一个图G称为Ore-(k)型图,如果任一对不相邻顶点“和v都有d(u)+d(v)≥|V(G)|+k(k为整数)。     

严格k可约n竞赛图的计数

如果n竞赛图T_n中任意n—k 1子竞赛图都是可约的,则T_n称为k可约的。如果T_n是k可约的,但不是k 1可约的,则T_n称为严格k可约的。设t(n)和s(n)分别表示n竞赛图和强n竞赛图的所有同构类的个数。对于给定正整数k,设     

关于竞赛图的弧哈密顿回路性

竞赛图T=(V,A)称为具有孤h回路性,若对任一条弧e∈A,T中都有一个长为h的回路通过e。设|V|=p,则弧p回路性也称作弧哈密顿回路性。邵品琮和张存铨在全国第二次图论学术交流会上提出如下的猜想:若T是弧哈密顿的,则T具有弧k回路性,k=h,h 1,…,p,其中,4≤h≤p—1。如将这个猜想记作c(h),显然有:若c(h)成立,则对任一h′,p—1≥h′≥h,c(h′)也成立;反之,若c(h)不成立,则对任一h′,4≤h′≤h,c(h′)也不成立。现在,我们证明了如下的结果。     

循环群的最小图

设c(n)是n阶循环群,自同构群与c(n)同构且顶点最少的图称为c(n)的最小图。本文要构造c(n)的最小图。当n=3,4,5和p~t(p≥7,p是素数)时,c(n)的最小图已被人们构造出来了。要构造c(n)的最小图,只要构造c(m)的最小图就行了。这里m为:     

n-可扩图的局部邻域条件娄定俊

设G是阶为v的图且具有完美对集。设n是正整数,满足n≤(v-2)/2.G称为n-可扩的,是说:G中任意n条独立边包含在G的一个完美对集中。 设G是一个图且v∈V(G)。定义N_k(v)={u|u∈V(G)且d(u,v)=k}。设u,v∈V(G)满足d(u,v)=2.记I(u,v)=|N(u)∩N(v)|。定义散度α~*(u,v)如下: n_(u+v)(W)=max{|S||w∈N(u)∩N(v),S是G[{w}∪N_G(w)]中包含u和v的独立集},