Degrees and cycles in digraphs |
| |
Authors: | M.-C. Heydemann |
| |
Affiliation: | Laboratoire de Recherche en Informatique, E.R.A. 452, Bâtiment 490, Université de Paris-Sud, 91405 Orsay, France |
| |
Abstract: | 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 , 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 . 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|