关于蕴含Ramsey数r_(pot)(K_n-ke,K_t-qe)问题  

Problem of Potentially Ramsey Number r_(pot)(K_n-ke,K_t-qe)

作　　者：马珩博 尹建华[1] 

机构地区：[1]海南大学信息科学技术学院,海南海口570228

出　　处：《海南大学学报（自然科学版）》2016年第4期319-323,共5页Natural Science Journal of Hainan University

基　　金：海南省自然科学基金(2016CXTD004)

摘　　要：对于一个非增的非负整数序列π=(d_1,d_2,,…,d_n),如果π是某个n阶简单图G的度序列,则称π是可图序列,并称G是π的一个实现.给定一个图G,可图序列π称为是蕴含G可图的,如果π有一个实现包含G作为子图.对于2个简单图G_1和G_2,存在一个最小的正整数k,使得对于任何k项可图序列π,都满足π是蕴含G_1可图的或者π的补序列π是蕴含G_2可图的,正整数k记为r_(pot)(G_1,G_2),称为是G_1和G_2的蕴含Ramsey数.Busch等[3]给出了r_(pot)(G,K_t)的一个下界,并确定了当n≥t≥3时,r_(pot)(K_n,K_t)的值.笔者进一步给出了r_(pot)(G,K_t-qe)的一个下界,并确定了当n≥t≥4时,r_(pot)(Kn,K_t-e)之值,其中K_t-qe表示从t阶完全图K_t中去掉q条独立边后所得到的图.For a non-increase non-negative integer sequence π = （d1, d2, ,…, d,, ） , if π is the degree sequence of a simple graph G on n vertices, π is graphic, and G is realization of or. If a graph was given, is said to be potentially G -graphic, π has a realization containing G as a subgraph. For two simple graphs, G1 and G2 , there is a minimal positive integer k , and for any graphic sequence π ,π is potential G1 -graphic or π is potential G2 - graphic. The positive integers k is denoted by rpot （ G1 , G2 ） , which is called the potential-Ramsey number of G1 and G2. Busch et al gave a lower bound of rpot（G,Kt） and determined the value of rpot（Kn,K,） when n ≥ t ≥ 3 . In the report, a lower bound of rpot（G,Kt - qe） was given and the value of rpot（Kn,Kt - e） was determined when n ≥ t≥ 4 , in which Kt - qe is a graph obtained from Kt by removing k independent edges.

关 键 词：蕴含Ramsey数 可图序列 实现 

分 类 号：O157.5[理学—数学]