**
Czechoslovak Mathematical Journal, Vol. 57, No. 2, pp. 705-724, 2007
**

#
On potentially $H$-graphic sequences

##
Meng-Xiao Yin, Jian-Hua Yin

* Meng-Xiao Yin*, College of Computer and Electronics Information, Guangxi University, Nanning, Guangxi 530004, China; * Jian-Hua Yin*, Department of Applied Mathematics, College of Information Science and Technology, Hainan University, Haikou, Hainan 570228, China, e-mail: ` yinjh@ustc.edu`

**Abstract:** For given a graph $H$, a graphic sequence $\pi=(d_1,d_2,\ldots,d_n)$ is said to be potentially $H$-graphic if there is a realization of $\pi$ containing $H$ as a subgraph. In this paper, we characterize the potentially $(K_5-e)$-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence $\pi$ to be potentially $K_5$-graphic, where $K_r$ is a complete graph on $r$ vertices and $K_r-e$ is a graph obtained from $K_r$ by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence $\pi$ to be potentially $K_6$-graphic.

**Keywords:** graph, degree sequence, potentially $H$-graphic sequence

**Classification (MSC 2000):** 05C07

**Full text** available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade.
To activate your access, please contact Myris Trade at myris@myris.cz.

Subscribers of Springer need to access the articles on their site, which is http://www.springeronline.com/10587.