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

Title:

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

Creator:

Yin, Jian-Hua

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:492d3803-326b-4a95-acc4-dc53e4602e58
uuid:492d3803-326b-4a95-acc4-dc53e4602e58

Subject:

graph, split graph, and degree sequence

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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).

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

863-867

Source:

Czechoslovak Mathematical Journal | 2012 Volume:62 | Number:3

Harvested from:

CDK

Metadata only:

false