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).
Let $r\ge 3$, $n\ge r$ and $\pi =(d_1,d_2,\ldots ,d_n)$ be a non-increasing sequence of nonnegative integers. If $\pi $ has a realization $G$ with vertex set $V(G)=\{v_1,v_2,\ldots ,v_n\}$ such that $d_G(v_i)=d_i$ for $i=1,2,\ldots , n$ and $v_1v_2\cdots v_rv_1$ is a cycle of length $r$ in $G$, then $\pi $ is said to be potentially $C_r''$-graphic. In this paper, we give a characterization for $\pi $ to be potentially $C_r''$-graphic.
A graph G is a k-tree if either G is the complete graph on k + 1 vertices, or G has a vertex v whose neighborhood is a clique of order k and the graph obtained by removing v from G is also a k-tree. Clearly, a k-tree has at least k + 1 vertices, and G is a 1-tree (usual tree) if and only if it is a 1-connected graph and has no K_{3} -minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of k-trees as follows: if G is a graph with at least k + 1 vertices, then G is a k-tree if and only if G has no K_{k+2} -minor, G does not contain any chordless cycle of length at least 4 and G is k-connected., De-Yan Zeng, Jian-Hua Yin., and Obsahuje seznam literatury
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.