On Potentially \({}_{k}C_\ell\)-Graphic Sequences

Jian-Hua Yin1, Gang Chen2, Guo-Liang Chen3
1Department of Computer Science, Hainan Normal University, Haikou 571158, China College of Information Science and Technology, Hainan University, Haikou 570228, China
2Department of Mathematics, Ningxia University, Yinchuan 750021, China
3Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China

Abstract

For given integers \( k \) and \( \ell \), \( 3 \leq k \leq \ell \), a graphic sequence \( \pi = (d_1, d_2, \dots, d_n) \) is said to be potentially \({}_{k}C_\ell\)-graphic if there exists a realization of \( \pi \) containing \( C_r \), for each \( r \), where \( k \leq r \leq \ell \) and \( C_r \) is the cycle of length \( r \). Luo (Ars Combinatoria 64(2002)301-318) characterized the potentially \( C_\ell \)-graphic sequences without zero terms for \( r = 3, 4, 5 \). In this paper, we characterize the potentially \(\prescript{}{k}C_\ell\)-graphic sequences without zero terms for \( k = 3, 4 \leq \ell \leq 5 \) and \( k = 4, \ell = 5 \).

Keywords: graph, degree sequence, potentially graphic sequence. MR subject classification(2000): 05C07, 05C38.