Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graph; split graph; degree sequence
graph; split graph; degree sequence
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).
References:
[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 10.1137/0110037 | MR 0148049 | Zbl 0168.44705
[2] Havel, V.: A remark on the existence of finite graphs. Čas. Mat. 80 (1955), 477-480 Czech. Zbl 0068.37202
[3] Lai, C. H., Hu, L. L.: Potentially $K_m-G$-graphical sequences: a survey. Czech. Math. J. 59 (2009), 1059-1075. DOI 10.1007/s10587-009-0074-7 | MR 2563577 | Zbl 1224.05105
[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 0553948 | Zbl 0483.05038
[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 10.1016/j.disc.2011.07.024 | MR 2832147 | Zbl 1238.05063
Search
Partner of
