关于唯一泛圈的图

所谓唯一泛圈的图(简称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]。     

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是点泛圈图。     

圈长唯一的最大图的边数

Erds于1975年提出了下列问题:设f(n)是有n个顶点的任何两个圈的长均不相等的图的最大可能的边数。试确定f(n)。 含有f(n)条边、没有两个等长圈的n个顶点的图称为圈长唯一的最大图。     

关于线图的泛圈性

线圈的概念是人所熟知的;记号L(G)表示简单图G的线圈。图G满足什么条件才能使得其线圈L(G)是Hamilton图?进一步,这些条件意味着线圈L(G)是泛圈图吗?这些问题是令人感兴趣的。 下列结果是已有的。 定理(Brualdi和Shanny) 如果G是有n≥4     

关于UC图

J.A.Bondy和U.S.R.Murty收集了若干尚未解决的问题,其中有R.C.Entringer于1973年提出的问题10:确定简单图G,使得对应于3≤l≤v的每一个l,G恰有一个长为l的圈(这里v表示图G的顶点数)。     

Hamilton图泛圈性的Ore类条件

在本文中,所有的图都是简单图,未定义的术语是常见的。众所周知,一个n阶图G,若对任何点对x,y;xy(?)E(G)总有d(x)+d(y)≥n,则G是Hamilton图(Ore,1960);进一步,G是泛圈图或二部图~K(n/2),n/2(Bondy,1971年)。     

型循环拟差集存在的一些必要条件

1973年,H.J.Rysert提出了Ⅰ型循环拟差集的概念,并且给出了它存在的一些必要条件。本文给出(v,k,λ)-Ⅰ型循环拟差集存在的其他必要条件,并利用所得到的结果,对满足v≡2(mod4),v<100的整数v,考察了(v,k,λ)-Ⅰ型循环拟差集的存在性问题。     

关于图的路连通性的几个结果

本文仅考虑无向简单图,若图G中任两点间均存在H路,则称图G是Hamilton连通的,记P_m(u,v)为图G中长为m—1的u—v路,若对图G中任两点u,v,G中均     

简单MCD图的边数的上界

用f(n)(f~*(n))表示具有n个顶点的没有两个等长圈的图(简单图)的最大可能的边数。确定f(n)的问题是Erd(?)s于1975年提出的至今尚未解决的难题。我们称具有n个顶点和f(n)(f~*(n))条边的图(简单图)为MCD图(简单MCD图)。在[2]中,我们已经证明f(n)     

可分解设计RGD(4,3;v)的存在性

所谓一个可分组设计GD(k,m;v)是指这样一个有序三元组(V,G,B),其中V是一个v元集,G是V的一些m子集(称作组)的集合,B是V的一些k子集的集合,使得 (ⅰ) G构成V的一个划分; (ⅱ) V中任意一对取自G中不同组的元素恰好在唯一的一个区组中相遇。 给定一个GD(k,m;v),若B中的若干个区组构成V的一个划分,则称为一个平行     

关于圈并的补图的色唯一性

设c_p表示长为p的圈,G1_(?)G_2表示图G_1与G_2的并图,(?)指图G的补图。Farrell和Whitehead猜测:圈的补图(?)(p≥5)是色唯一的。在本文中我们证明了如下的主要定理。 定理 设G是2正则图且不合‘,和‘.为其子图,则G是匹配唯一的当且仅当(?)是色唯一的。     

关于最大唯一圈图

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

Ore-2型图中存在两个边不相重的Hamilton圈

本文讨论的图都是无向的简单图。设G是一个图,分别用V(G)和E(G)表示图G的顶点集和边集。又设“、v∈V(G),用d(v)表示v的次数,用vu表示连结u、v的边。     

关于竞赛图中王的一些结果

1953年Landau引进了竞赛图中“王”的概念:如果竞赛图T的顶点v能通过长至多为2的有向路到达T的其他各个顶点,则称v 为王.他证明了,竞赛图中出度最大的顶点是王.1980年Maurer 证明了,对于整数n≥k≥1,不存在恰有k 个王和n 个顶点的竞赛图的充要条件是k=2或k=n=4.1982年Bridgland 和Reid 引进了下述概念:设T 是竞赛图,t、c     

一个k-Hamilton-良好的序列

设G是一个无向简单图,t是一个正整数。令(?)_t(G)={Y(?)V(G)|Y是G的独立集,|Y|=t}。对于Y∈(?)_t(G),i∈{0,1,2,…,t},令S_i(Y)={v∈V(G)||N(v)∩Y|=i},s_i(Y)=|S_i(Y)|。1990年,陈冠涛等(私人通信)引入了如下概念。     

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

本文讨论无向简单图。设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中弦的最大数目。     

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

正则二部竞赛图的弧泛回路性质

二部竞赛图D=(V,A)即是一个完全二部定向图,称D具有弧k回路性质,若D中的每一条弧均在k回路上,这里k为偶数,且4≤k≤|V(D)|,若对所有的偶数k4≤k≤|V(D)|,D总是具有弧k回路性质,则称D具有弧泛回路性质。     

不可分离外平面地图节点剖分计数

全文只研究带根的地图。记N为所有有根不可分离外平面地图的集合。对于N∈N,令v=v(N)是根节点,r=r(N)是根边,m(N)是节点v的次,和n_i(N),i≥1,次为i的非根节点数。进而,应该指出,仅由一个节点而无边所成的地图,即节点地图,和仅有一边     

关于边不交的Hamiltoh圈

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