Geodesic
A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially $S_{r,s}$-graphic
Czechoslovak Mathematical Journal, Tome 62 (2012) no. 3, pp. 863-867

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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).
DOI : 10.1007/s10587-012-0051-4
Classification : 05C07, 05C69, 05C70
Keywords: graph; split graph; degree sequence 
@article{10_1007_s10587_012_0051_4,
     author = {Yin, Jian-Hua},
     title = {A {Havel-Hakimi} type procedure and a sufficient condition for a sequence to be potentially $S_{r,s}$-graphic},
     journal = {Czechoslovak Mathematical Journal},
     pages = {863--867},
     publisher = {mathdoc},
     volume = {62},
     number = {3},
     year = {2012},
     doi = {10.1007/s10587-012-0051-4},
     mrnumber = {2984639},
     zbl = {1265.05130},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0051-4/}
}
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
SP  - 863
EP  - 867
VL  - 62
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0051-4/
DO  - 10.1007/s10587-012-0051-4
LA  - en
ID  - 10_1007_s10587_012_0051_4
ER  - 
%0 Journal Article
%A Yin, Jian-Hua
%T A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially $S_{r,s}$-graphic
%J Czechoslovak Mathematical Journal
%D 2012
%P 863-867
%V 62
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-012-0051-4/
%R 10.1007/s10587-012-0051-4
%G en
%F 10_1007_s10587_012_0051_4
Yin, Jian-Hua. A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially $S_{r,s}$-graphic. Czechoslovak Mathematical Journal, Tome 62 (2012) no. 3, pp. 863-867. doi: 10.1007/s10587-012-0051-4

Cité par Sources :