首页 | 本学科首页   官方微博 | 高级检索  
     


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 ?(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.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号