Potentially Kr+1-p-graphic sequences

被引:0
作者
Yin, Jian-Hua [1 ]
Li, Jiong-Sheng [2 ]
机构
[1] Hainan Univ, Coll Informat Sci & Technol, Dept Appl Math, Haikou 570228, Hainan, Peoples R China
[2] Univ Sci & Technol China, Dept Math, Hefei 230026, Anhui, Peoples R China
关键词
graph; degree sequence; potentially K(r+1)(-p)-graphic sequence; SMALLEST DEGREE SUM; EXTREMAL PROBLEM; GRAPHIC SEQUENCES;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let 0 <= p <= [r+1/2] and sigma(K(r+1)(-p), n) be the smallest even 2 integer such that each n-term graphic sequence with term sum at least sigma(K(r+1)(-p), n) has a realization containing K(r+1)(-p) as a subgraph, where K(r+1)(-p) is a graph obtained from a complete graph K(r+1) on r + 1 vertices by deleting p edges which form a matching. In this paper, we determine sigma(K(r+1)(-p), n) for r >= 2, 1 <= p <= [r+1/2] and n >= 3r + 3. As a corollary, we also determine sigma(K(1n), (2t), n) for t >= 1 and n >= 3s + 6t, where K(1n), (2t) is an r(1) x r(2) x ... x r(s+t) complete (s + t)-partite graph with r(1) = r(2) = ... = r(s) = 1 and r(s+1) = r(s+2) = ... = r(s+t) = 2 and sigma(K(1n), (2t), n) is the smallest even integer such that each n-term graphic sequence with term sum at least sigma(K(1n), (2t), n) has a realization containing K(r+1)(-p) as a subgraph.
引用
收藏
页码:405 / 409
页数:5
相关论文
共 15 条
[1]  
Chen G., 2003, J. XuZhou Normal University, V21, P5
[2]  
Erdos P., 1960, Mat. Lapok (N.S.), V11, P264
[3]  
Erdos P., 1991, Graphs realizing the same degree sequence and their respective clique numbers, graph theory, combinatorics and applications, Vi, P439
[4]  
Gould R.J., 1999, Combinatorics, Graph Theory, and Algorithms, V1, P451
[5]  
Lai C., 2001, Australas. J. Combin, V24, P123
[6]   The Erdos-Jacobson-Lehel conjecture on potentially Pk-graphic sequence is true [J].
Li, JS ;
Song, ZX ;
Luo, R .
SCIENCE IN CHINA SERIES A-MATHEMATICS PHYSICS ASTRONOMY, 1998, 41 (05) :510-520
[7]   An extremal problem on the potentially Pk-graphic sequences [J].
Li, JS ;
Song, ZX .
DISCRETE MATHEMATICS, 2000, 212 (03) :223-231
[8]  
LI JS, ACTA MATH S IN PRESS
[9]  
LI JS, 1998, J GRAPH THEOR, V29, P63
[10]  
Yin JH, 2005, ARS COMBINATORIA, V74, P213