A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially -graphic
Czechoslovak Mathematical Journal (2012)
- Volume: 62, Issue: 3, page 863-867
- ISSN: 0011-4642
Access Full Article
top
Abstract
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.