有向图的Hamilton有向圈和通路

<正> Nash-Williams猜想([1];[2]p.202):一个无环的有向图D,它的最小出入度为k,顶点数为p,当5≤p≤2k时,D中有弧不重的两个Hamilton有向圈. 本文将指出:当5≤p≤2k时,D中必有弧不重的一个Hamilton有向圈和一个Hamilton通路.     

定向图的Hamilton有向圈

An oriented graph is a directed graph without loop and with at most one are be-tween each pair of vertices. Let D be an oriented graph of order n such that the in-degree and outdegree of each vertex is at least k. Jackson proved that if n≤2k 2, andk≥2, D contains a Hamiltonian cycle. In this paper, we show that if n≤2k 3, andk≥3, D contains a Hamiltonian cycle.     

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

设G=(V,E)是2-边连通图,若对每个点v∈V,G-v不是2-边连通图,则称G是临界2-边连通图. 本文证明了p阶临界2-边连通图的最大边数是 7, P=6; (1/8)(P~2+4p) p=0(mod 4); f(p)= (1/8)(P~2+2p+13) p=1(mod 4); (1/8)(P~2+28) p=(2mod 4),p≠6 (1/8)(P~2+2p+9) p=3(mod 4)。并且给出了达到最大边数的极值图.     

一类竞赛图的弧泛回路

Alspach证明了正则竞赛图具有弧泛回路的性质。本文将指出有更大一类竞赛图也具有弧泛回路的性质。并且正则竞赛图也显然属于这一类竞赛图。这类竞赛图满足两个条件:弧三回路和|T|≤4k-3(k为竞赛图T的最小出、入度)。     

二部定向图的最长通路和圈

Let D be a bipartite oriented graph in which the indegree and outdegree of each vertex are at least k. The result given in this paper is that D contains either a cycle of length at least 4k or a path of length at least 4k + 1. Jackson [1] declared that: if |V(D) |≤4k,D contains a Hamiltonian cycle. Evidently, the result Of this paper implies the result given by Jackson.