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


Some Ramsey numbers for directed graphs
Authors:JC Bermond
Institution:Centre de Mathématique Sociale, 54 Bd Raspail, 75.270 Paris Cedex 06, France
Abstract:Given k directed graphs G1,…,Gk the Ramsey number R(G1,…, Gk) is the smallest integer n such that for any partition (U1,…,Uk) of the arcs of the complete symmetric directed graph Kn, there exists an integer i such that the partial graph generated by U1 contains G1 as a subgraph. In the article we give a necessary and sufficient condition for the existence of Ramsey numbers, and, when they exist an upper bound function. We also give exact values for some classes of graphs. Our main result is: R(Pn,….Pnk-1, G) = n1…nk-1 (p-1) + 1, where G is a hamltonian directed graph with p vertices and Pni denotes the directed path of length nt
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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