一类新的泛圈图

本文所说的图都是简单无向图。未定义的术语和记号参见[2]。设 G=(V,E)的 n 阶图(n≥3),若 G 中含有 Hamilton 圈,则称 G 是 H-图。若G 中含有从3到 n 的所有长度的圈,则称 G 为泛圈图。如下两个定理是众所周知的。定理1 (Ore,1960)。若在 n 阶图 G 中,有uv(?)E(G)(?)d(u) d(v)≥n,则 G 是 H-图。     

汉米尔顿图泛圈性的奥尔型条件

本文所说的图是简单图,未定义的术语见[1,2].n 阶图 G,n≥3,若有长为 n 的圈,则说 G 是汉米尔顿图;若对每个 k,3≤k≤n,G 含有长为 k 的圈,则说 G 是泛圈图.定理1.在 n 阶图 G 中,若对任何点对 x,y∈V(G),xy(?)E(G),都有 d(x)+d(y)≥n,则 G 是汉米尔顿图.     

ON PANCYCLIC LINE GRAPHS

In this paper,we give a best possible Ore-like condition for a graph so that its line graph ispancyclic or vertex pancyclic.     

THE BINDING NUMBER OF A GRAPH AND ITS TRIANGLE

In this paper we prove the following conjecture of Woodall:if bind(G)≥3/2,then Gcontains a triangle.Moreover,we also prove that if bind(G)≥3/2,then each vertex is contained ina 4-cycle,each edge is contained in a 5-cycle when V(G)≥11,and there exists a 6-cycle in G.     

The binding number of a graph and its pancyclism

The binding number is an important parameter of a graph.The binding number of a graph G,bind (G),is the largest real number c such that|N(X)|=min(c|X|,|V(G)|) for every X(?)V(G).In this paper,we prove the Woodall's conjecture:In bind (G)≥3/2,then G is pancyclic;andobtain some interesting results.     

平方图的汉米尔顿性

一个图 G 的平方图(记作 G~2),是在 G 中把所有距离为2的点对用边相邻接而形成的图.本文主要结果是:定理.如果 G 是连通,无 S(K_(1,3))导出子图的图,则 G~2是顶点泛圈图.这样,Gould 和 Jacobson 提出的两个猜想得到证明.结合这一方向上已有的工作,平方图的汉米尔顿问题基本上得到满意的解决.     

3—连通局部连通无爪图是泛连通图

本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立.     

围长对是(4,5)的最小正则图

我们把围长对是(g,h)的 k-正则图称为(k;g,h)-图;(k;g,h)-图的顶点的最少数目用 f(k;g,h)表示.本文证明了(?)我们还构造了最小(2s+1;4,5)-图,s≥1的无限族.这样,我们就完全解决了 Harary和 Kovács 提出的问题1.