Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size (Q2581629)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size |
scientific article |
Statements
Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size (English)
0 references
10 January 2006
0 references
The authors provide two new sufficient conditions on a degree sequence that can correspond to a graph containing a clique of order \(r+1\): a graphic sequence \(d_1\geq\cdots\geq d_n\) is a degree sequence of a graph with clique of order \(r+1\) if \(n\geq r+1\), \(d_i\geq 2r_i\) for \(i\leq r-1\) and \(d_{r+1}\geq r\), or if \(n\geq 2r+2\), \(d_{r+1}\geq r\) and \(d_{2r-2}\geq r-1\). The established sufficient conditions are used to reprove several previous results in the area.
0 references
graphic sequences
0 references
graphs with cliques
0 references