A characterization for a graphic sequence to have a realization containing a desired cycle

Abstract

Let r ≥ 3 and S(r) be the set of all circular arrangements of 1,2,⋯ ,r. It is well known that S(r) = {i₁i ₂⋯⋯.⋯..i_r|i₁ = 1 and i₂i₃⋯⋯⋯⋯.i_r is an arrangement of 2,3,⋯ ,r} and |S(r)| = (r -1)(r 2)-l. Let α = i ₁i₂⋯⋯⋯⋯i_r ⋯S(r) and φ = (d₁d₂⋯d_n) be a graphic sequence with n ≥ r. If ir has a realization G with vertex set V(G) = {1,2, ⋯,n} such that d_G(i) = d_i for i = 1,2, ⋯,n and i₁i₂⋯..i_ri₁ is a cycle of length r in G, then φ is said to be potentially C _r^α-graphic. We use A(α) to denote the set of all potentially C_r^α-graphic sequences. In this paper, we give a characterization for φ ⋯∩α⋯S(τ) A(α). In other words, we characterize φ such that φ is potentially G_r^α-graphic for each α⋯ S(r).