A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r,s -graphic
Jian-Hua Yin · Czechoslovak Mathematical Journal · 2012
The split graph K r + $$\overline {{K_s}} $$ on r+s vertices is denoted by S r,s . A non-increasing sequence π = (d 1, d 2, …, d n ) of nonnegative integers is said to be potentially S r,s -graphic if there exists a realization of π containing S r,s as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for π to be potentially S r,s -graphic. They are extensions of two theorems due to A.R.Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series 4 (1979), 251–267 and An Erdős-Gallai type result on the clique number of a realization of a degree sequence, unpublished).