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
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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).
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},
     year = {2012},
     volume = {62},
     number = {3},
     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
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
%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

[1] Hakimi, S. L.: On realizability of a set of integers as degrees of the vertices of a linear graph. I. J. Soc. Ind. Appl. Math. 10 (1962), 496-506. | DOI | MR | Zbl

[2] Havel, V.: A remark on the existence of finite graphs. Čas. Mat. 80 (1955), 477-480 Czech. | Zbl

[3] Lai, C. H., Hu, L. L.: Potentially $K_m-G$-graphical sequences: a survey. Czech. Math. J. 59 (2009), 1059-1075. | DOI | MR | Zbl

[4] 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. | MR | Zbl

[5] Rao, A. R.: An Erdős-Gallai type result on the clique number of a realization of a degree sequence. Unpublished.

[6] Yin, J. H.: A Rao-type characterization for a sequence to have a realization containing a split graph. Discrete Math. 311 (2011), 2485-2489. | DOI | MR | Zbl

Cité par Sources :