γ-可图序列与γ-完全子图  

r-Graphic Sequences and r-Complete Subgraphs

作　　者：尹建华[1] 

机构地区：[1]海南大学信息学院数学系,海口570228

出　　处：《数学学报（中文版）》2013年第3期369-380,共12页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金资助项目(11161016,11261015,10861006)

摘　　要：一个r-图是一个无环的无向图,其中任何两个顶点之间至多被r条边连接.一个m+1个顶点的r-完全图,记为K_(m+1)^((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)^((r))可图的如果π有一个实现包含K_(m+1)^((r))作为子图(π的每一个实现包含K_(m+1)^((r))作为子图).设σ(K_(m+1)^((r)),n)(τ(K_(m+1)^((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)~n d_i≥t是蕴含(强迫)K_(m+1)^((r))-可图的.易见,σ(K_(m+1)^((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)^((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)^((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m^2+3m+1-[(m^2+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)^((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)^((r)),n)之值.An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m ＋ 1 vertices, denoted by K（τ）m＋1, is an r-graph on m ＋ 1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π = （d1, d2,..., dn） of nonnegative integers is said to be r-graphic if it is the degree sequence of some r-graph on n vertices. An r-graphic sequence π is said to be potentially （resp. forcibly） K（τ）m＋1-graphic if π has a realization containing K（τ）m＋1 as a subgraph （resp. every realization of π contains K（τ）m＋1 as a subgraph）. Let σ（ K（τ）m＋1, n） （resp. K（τ）m＋1, n）） denote the smallest even integer t n such that each r-graphic sequence π = （d1, d2,..., dn） with ∑i=1ndi≥ t is potentially （resp. forcibly） K（τ）m＋1-graphic. Clearly,σ（ K（τ）m＋1, n） is an extension from 1-graph to r-graph of a conjecture due to Erdos et al and τ（K（τ）m＋1,n） is an extension from 1-graph to r-graph of the classical Turan＇s theorem. In this paper, we give two simple sufficient conditions for an r-graphic sequence to be potentially K（τ）m＋1-graphic, which imply two main results due to Yin and Li （Discrete Math., 2005, 301： 218-227） and the value of σ（K（τ）m＋1, n） for n 〉 max{m2＋3m＋1-[m2＋m/τ],2m＋1＋[m/τ]}. Moreover, we also determine the value of τ（K（τ）m＋1, n） for n 〉 m ＋ 1.

关 键 词：r-图 r-完全图 r-可图序列 

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