A characterization for a graphic sequence to be potentially C-r-graphic

作者：Yin JianHua^*

来源：Science China Mathematics, 2010, 53(11): 2893-2905.

DOI：10.1007/s11425-010-3124-6

• graph
• cycle
• degree sequence

Let r >= 3, n >= r and pi = (d(1), d(2), ... , d(n)) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence pi such that G contains C-r (a cycle of length r) as a subgraph, then pi is said to be potentially C-r-graphic. Li and Yin (2004) posed the following problem: characterize pi = (d(1), d(2), ... , d(n)) such that pi is potentially C-r-graphic for r >= 3 and n >= r. Rao and Rao (1972) and Kundu (1973) answered this problem for the case of n = r. In this paper, this problem is solved completely.

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