关于路与完全图的蕴含Ramsey数
Potential-Ramsey Numbers of Paths and Complete Graphs
-
摘要: 对于一个n项非增的非负整数序列π=(d1, …, dn),若其是某个n阶简单图G的度序列,则称π是可图序列,并称G是π的一个实现.给定一个图H,如果π的某个实现包含H作为子图,则称π是蕴含H可图的.给出了当2≤n≤5, t≥2时rpot(Pn, Kt)的确切值,从而完整确定了rpot(Pn, Kt)值.Abstract: A non-increasing sequence π=(d1,…,dn)of nonnegative integers is a graph sequence if it is realizable by a simple graph G on n vertices. In this case, G is referred to as a realization of π. Given a graph H, if π has a realization containing H as a subgraph, a graphic sequence π is potentially H- graphic. When 2≤n≤5, t≥2 , the exact value for rpot(Pn, Kt)will be determined completely.