# A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially ${S}_{r,s}$-graphic

Czechoslovak Mathematical Journal (2012)

- Volume: 62, Issue: 3, page 863-867
- ISSN: 0011-4642

## Access Full Article

top## Abstract

top## How to cite

topYin, Jian Hua. "A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially $S_{r,s}$-graphic." Czechoslovak Mathematical Journal 62.3 (2012): 863-867. <http://eudml.org/doc/246637>.

@article{Yin2012,

abstract = {The split graph $K_r+\overline\{K_s\}$ on $r+s$ vertices is denoted by $S_\{r,s\}$. A non-increasing sequence $\pi =(d_1,d_2,\ldots ,d_n)$ of nonnegative integers is said to be potentially $S_\{r,s\}$-graphic if there exists a realization of $\pi $ containing $S_\{r,s\}$ as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for $\pi $ 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).},

author = {Yin, Jian Hua},

journal = {Czechoslovak Mathematical Journal},

keywords = {graph; split graph; degree sequence; split graph; degree sequence},

language = {eng},

number = {3},

pages = {863-867},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially $S_\{r,s\}$-graphic},

url = {http://eudml.org/doc/246637},

volume = {62},

year = {2012},

}

TY - JOUR

AU - Yin, Jian Hua

TI - A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially $S_{r,s}$-graphic

JO - Czechoslovak Mathematical Journal

PY - 2012

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 62

IS - 3

SP - 863

EP - 867

AB - The split graph $K_r+\overline{K_s}$ on $r+s$ vertices is denoted by $S_{r,s}$. A non-increasing sequence $\pi =(d_1,d_2,\ldots ,d_n)$ of nonnegative integers is said to be potentially $S_{r,s}$-graphic if there exists a realization of $\pi $ containing $S_{r,s}$ as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for $\pi $ 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).

LA - eng

KW - graph; split graph; degree sequence; split graph; degree sequence

UR - http://eudml.org/doc/246637

ER -

## References

top- Hakimi, S. L., 10.1137/0110037, J. Soc. Ind. Appl. Math. 10 (1962), 496-506. (1962) Zbl0168.44705MR0148049DOI10.1137/0110037
- Havel, V., A remark on the existence of finite graphs, Čas. Mat. 80 (1955), 477-480 Czech. (1955) Zbl0068.37202
- Lai, C. H., Hu, L. L., 10.1007/s10587-009-0074-7, Czech. Math. J. 59 (2009), 1059-1075. (2009) Zbl1224.05105MR2563577DOI10.1007/s10587-009-0074-7
- Rao, A. R., The clique number of a graph with a given degree sequence, Graph theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes 4 (1979), 251-267. (1979) Zbl0483.05038MR0553948
- Rao, A. R., An Erdős-Gallai type result on the clique number of a realization of a degree sequence, Unpublished.
- Yin, J. H., 10.1016/j.disc.2011.07.024, Discrete Math. 311 (2011), 2485-2489. (2011) Zbl1238.05063MR2832147DOI10.1016/j.disc.2011.07.024

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.