The smallest degree sum that yields potentially Kr,r-graphic sequences

被引：0

作者：

尹建华

李炯生

机构：

来源：

Science China Mathematics | 2002年 / 06期

基金：

中国国家自然科学基金;

关键词：

graph; degree sequence; potentially Kr; r-graphic sequence;

D O I：

暂无

中图分类号：

O157 [组合数学（组合学）];

学科分类号：

070104 ;

摘要：

We consider a variation of a classical Turan-type extremal problem as follows: Determine the smallest even integer α(Kr,r,n) such that every n-term graphic sequence π = (d1,d2,…,dn) with term sum α(π) = d1 + d2 +… + dn ≥ α(Kr,r, n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. π has a realization G containing KT.r as its subgraph. In this paper, the values α(Kr,r,n) for even r and n ≥ 4r2 - r- 6 and for odd r and n≥4r2+3r-8 are determined.

引用

页码：694 / 705

页数：12