A Note for Integer Sequences to be Potentially \(K_{r+I}\)-Graphic

Jian-Hua Yint1
1Department of Mathematics, College of Information Science and Technology, Hainan University, Haikou 570228, P.R. China.

Abstract

Let \( K_{r+1} \) be the complete graph on \( r+1 \) vertices and let \( \pi = (d_1, d_2, \ldots, d_n) \) be a non-increasing sequence of nonnegative integers. If \( \pi \) has a realization containing \( K_{r+1} \) as a subgraph, then \( \pi \) is said to be potentially \( K_{r+1} \)-graphic. A.R. Rao obtained an Erdős-Gallai type criterion for \( \pi \) to be potentially \( K_{r+1} \)-graphic. In this paper, we provide a simplification of this Erdős-Gallai type criterion. Additionally, we present the Fulkerson-Hoffman-McAndrew type criterion and the Hasselbarth type criterion for \( \pi \) to be potentially \( K_{r+1} \)-graphic.

Keywords: graph, degree sequence, potentially K,41-graphic sequence. Mathematics Subject Classification(2000): 05C07