| Title:
|
A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially $S_{r,s}$-graphic (English) |
| Author:
|
Yin, Jian-Hua |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
62 |
| Issue:
|
3 |
| Year:
|
2012 |
| Pages:
|
863-867 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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). (English) |
| Keyword:
|
graph |
| Keyword:
|
split graph |
| Keyword:
|
degree sequence |
| MSC:
|
05C07 |
| MSC:
|
05C69 |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 1265.05130 |
| idMR:
|
MR2984639 |
| DOI:
|
10.1007/s10587-012-0051-4 |
| . |
| Date available:
|
2012-11-10T21:23:27Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143030 |
| . |
| Reference:
|
[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. Zbl 0168.44705, MR 0148049, 10.1137/0110037 |
| Reference:
|
[2] Havel, V.: A remark on the existence of finite graphs.Čas. Mat. 80 (1955), 477-480 Czech. Zbl 0068.37202 |
| Reference:
|
[3] Lai, C. H., Hu, L. L.: Potentially $K_m-G$-graphical sequences: a survey.Czech. Math. J. 59 (2009), 1059-1075. Zbl 1224.05105, MR 2563577, 10.1007/s10587-009-0074-7 |
| Reference:
|
[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. Zbl 0483.05038, MR 0553948 |
| Reference:
|
[5] Rao, A. R.: An Erdős-Gallai type result on the clique number of a realization of a degree sequence.Unpublished. |
| Reference:
|
[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. Zbl 1238.05063, MR 2832147, 10.1016/j.disc.2011.07.024 |
| . |
