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:

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
Subscribers of Springer need to access the articles on their site, which is

[Previous Article] [Next Article] [Contents of This Number] [Contents of Czechoslovak Mathematical Journal]