Jian-Hua YIN
A non-increasing sequence π=(d1, d2,…, dn) of nonnegative integers is said to be potentially hamiltonian-graphic (resp. potentially pancyclic-graphic) if it is realizable by a simple graph on n vertices containing a hamiltonian cycle (resp. containing cycles of every length from 3 to n). A.R. Rao and S.B. Rao (J. Combin. Theory Ser.B, 13(1972), 185-191) and Kundu (Discrete Math., 6(1973), 367-376) presented a characterization of π=(d1, d2,…, dn) that is potentially hamiltonian-graphic. S.B. Rao (Lecture Notes in Math., No. 855, Springer Verlag, 1981, 417-440, Unsolved Problem 2) further posed the following problem:present a characterization of π=(d1, d2,…, dn) that is potentially pancyclic-graphic. In this paper, we first give solution to this problem for the case of 4 ≤ n ≤ 11. Moreover, we also show that a near regular graphic sequence π=(d1, d2,…, dn) with dn ≥ 3 is potentially pancyclic-graphic.