A non-increasing sequenceπ=(d_1,d_2,···,d_n)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 ...A non-increasing sequenceπ=(d_1,d_2,···,d_n)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π=(d_1,d_2,···,d_n)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π=(d_1,d_2,···,d_n)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π=(d_1,d_2,···,d_n)with dn≥3 is potentially pancyclic-graphic.展开更多
基金Supported by National Natural Science Foundation of China(Grant No.11561017)Natural Science Foundation of Hainan Province(Grant No.2016CXTD004)
文摘A non-increasing sequenceπ=(d_1,d_2,···,d_n)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π=(d_1,d_2,···,d_n)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π=(d_1,d_2,···,d_n)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π=(d_1,d_2,···,d_n)with dn≥3 is potentially pancyclic-graphic.
