Degrees and cycles in digraphs
Degrees and cycles in digraphs
复制标题
有向图中的度数和周期
DOI：
10.1016/0012-365x(82)90020-6
复制
发表时间：
1982
影响因子：
0.8
通讯作者：
M. Heydemann
中科院分区：
文献类型：
--
作者：
M. Heydemann
本文给出了强有向图中顶点的总度的条件，这意味着存在长度至少为<$（n− 1）h <$+ 1的圈，其中n是图的顶点数，h是整数，1 <$h <$n− 1.同样的条件意味着存在一条长度为+的路。在强定向图（反对称有向图）的情况下，我们改进了这些条件。在这两种情况下，我们表明，给定的条件是最好的可能。
In this article, we give conditions on the total degrees of the vertices in a strong digraph implying the existence of a cycle of length at least⌈(n− 1) h⌉+ 1, where n is the number of vertices of the graph and h an integer, 1⩽ h⩽ n− 1. The same conditions imply the existence of a path of length⌈(n− 1) h⌉+⌈(n− 2) h⌉. In the case of strong oriented graphs (antisymmetric digraphs) we improve these conditions. In both cases, we show that the given conditions are the best possible.