The Erds-Jacobson-Lehel conjecture on potentially Pk-graphic sequence is true

被引:1
|
作者
李炯生
宋梓霞
罗荣
机构
关键词
graph; graphic sequence; off diagonal leftmost matrix; potentially P k graphic sequence;
D O I
暂无
中图分类号
O157.5 [图论];
学科分类号
070104 ;
摘要
A variation in the classical Turn 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 π=(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 π is said to be potentially P k graphic if it has a realization G having property P k . The problem: determine the smallest positive even number σ(k,n) such that every n term graphic sequence π=(d 1,d 2,...,d n) without zero terms and with degree sum σ(π)=d 1+d 2+...+d n at least σ(k,n) is potentially P k graphic has been proved positive.
引用
收藏
页码:510 / 520
页数:11
相关论文
共 9 条