Premium
Graphic sequences that have a realization with large clique number
Author(s) -
Mubayi Dhruv
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(200005)34:1<20::aid-jgt3>3.0.co;2-v
Subject(s) - combinatorics , realization (probability) , mathematics , graph , clique , sequence (biology) , clique graph , element (criminal law) , discrete mathematics , line graph , graph power , statistics , genetics , political science , law , biology
We prove that for k ≥ 5, every (2 k + 2)‐element graphic sequence of positive terms with sum at least 4 k ( k − 1) can be realized by a graph containing K k +1 . Also, this bound is sharp. Furthermore, for 2 k + 3 ≤ n ≤ k (5 k − 11)/(2 k − 4), we construct a graphic n ‐element positive sequence with sum (2 k − 4)(2 k − 1) + 2( n − 1) that has no realization containing K k +1 . This construction partially answers a question of Erdős et al. in the negative. © John Wiley & Sons, Inc. J Graph Theory 34: 20–29, 2000