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: , where G is a hamltonian directed graph with p vertices and denotes the directed path of length nt |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|