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

Yin, Jian-Hua

doi:10.1007/s10587-012-0051-4

Geodesic

Parcourir par

A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially

S_{r, s}

-graphic

Yin, Jian-Hua

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

Résumé

The split graph

K_{r} + \overset{―}{K_{s}}

r + s

vertices is denoted by

S_{r, s}

. A non-increasing sequence

π = (d_{1}, d_{2}, \dots, 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).

MR Zbl

DOI : 10.1007/s10587-012-0051-4

Classification : 05C07, 05C69, 05C70
Mots-clés : 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 = {https://geodesic-test.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  - https://geodesic-test.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 https://geodesic-test.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. https://geodesic-test.mathdoc.fr/articles/10.1007/s10587-012-0051-4/

Cité par Sources :