The Erdos-Jacobson-Lehel conjecture on potentially Pk-graphic sequence is true

被引:54
作者
Li, JS [1 ]
Song, ZX [1 ]
Luo, R [1 ]
机构
[1] Univ Sci & Technol China, Dept Math, Hefei 230026, Peoples R China
来源
SCIENCE IN CHINA SERIES A-MATHEMATICS PHYSICS ASTRONOMY | 1998年 / 41卷 / 05期
关键词
graph; graphic sequence; off-diagonal leftmost matrix; potentially P-k-graphic sequence;
D O I
10.1007/BF02879940
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A variation in the classical Turan extremal problem is studied. A simple graph G of order n is said to have property P-k if it contains a clique of size k + 1 as its subgraph. An n-term nonincreasing nonnegative integer sequence pi = (d(1), d(2),..., d(n)) is said to be graphic if it is the degree sequence of a simple graph G of order n and such a graph G is referred to as a realization of;(. A graphic sequence a is said to be potentially PI-graphic if it has a realization G having property P-k. The problem: determine the smallest positive even number sigma(k, n) such that every n-term graphic sequence pi =(d(1), d(2),..., d(n)) without zero terms and with degree sum sigma(pi) = d(1) + d(2) + ... + d(n) at least sigma(k, n) is potentially P-k-graphic has been proved positive.
引用
收藏
页码:510 / 520
页数:11
相关论文
共 8 条
  • [1] BERGE C, 1973, GRAPHS HYPERGRAPHS, P115
  • [2] Bollobas B., 1978, EXTREMAL GRAPH THEOR
  • [3] ERDOS P, 1991, GRAPH THEORY COMBINA, V1, P439
  • [4] FULKERSON D. R., 1960, Pacific J. Math., V10, P831, DOI DOI 10.2140/PJM.1960.10.831
  • [5] Kleitman D. J., 1973, Discrete Mathematics, V6, P79, DOI 10.1016/0012-365X(73)90037-X
  • [6] Li J., 1994, ADV MATH, V23, P193
  • [7] Rao A. R., 1979, LECT NOTES SERIES, V4, P251
  • [8] RAO SB, 1981, LECT NOTES MATH, V885, P417, DOI DOI 10.1007/BFB0092288