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

作者：Yin, Jian-Hua^*; Wang, Ye

来源：Utilitas Mathematica, 2011, 86: 79-86.

• graph
• cycle
• degree sequence

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(1) i(2) ... i(r)vertical bar i(1) = 1 and i(2)i(3) ... i(r) is an arrangement of 2,3, ... , r} and vertical bar S(r)vertical bar = (r - 1)(r - 2) ... 1. Let alpha = i(1)i(2) ... i(r) is an element of S(r) and pi = (d(1), d(2), ... ,d(n)) be a graphic sequence with n >= r. If pi 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(1)i(2) ... i(r)i(r) is a cycle of length r in G, then pi is said to be potentially C(r)(alpha)-graphic. We use A(alpha) to denote the set of all potentially C(r)(alpha)-graphic sequences. In this paper, we give a characterization for pi is an element of boolean AND(alpha is an element of S(r))A(alpha). In other words, we characterize pi such that pi is potentially C(r)(alpha)-graphic for each alpha is an element of S(r).

• 出版日期2011-11
• 单位海南大学