A characterization for a graphic sequence to be potentially C_r-graphic  

作　　者：YIN JianHua Department of Mathematics, College of Information Science and Technology, Hainan University, Haikou 570228, China 

出　　处：《Science China Mathematics》2010年第11期2893-2905,共13页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China (Grant No.10861006);the 2009 Scientific Research Foundation of Hainan University (Grant No. hd09xm87);the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry of China (Grant No.2009-1001)

摘　　要：Let r 3, n r and π = (d1, d2, . . . , dn) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence π such that G contains Cr (a cycle of length r) as a subgraph, then π is said to be potentially Cr-graphic. Li and Yin (2004) posed the following problem: characterize π = (d1, d2, . . . , dn) such that π is potentially Cr-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.Let r 3, n r and π = (d1, d2, . . . , dn) be a graphic sequence. If there exists a simple graph G on n vertices having degree sequence π such that G contains Cr (a cycle of length r) as a subgraph, then π is said to be potentially Cr-graphic. Li and Yin (2004) posed the following problem: characterize π = (d1, d2, . . . , dn) such that π is potentially Cr-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.

关 键 词：GRAPH CYCLE DEGREE SEQUENCE 

分 类 号：O157.5[理学—数学]