A graph is Hamiltonian if it contains a cycle using all vertices .If an n-vertex graph G contains a cycle of length k for every k such that 3≤k≤n, then it is called pancyclic .A graph G is called weakly pancyclic if it contains cycles of all lengths between its girth and circumference .In 1981,Haggkvist, Faudree andSchelp states that a Hamiltonian graph of order n and size at least (n-1)2/41 isweakly pancyclic or bipartite .Brandt improved the assertion in 1977,he proved that every non-bipartite graph of the stated order and size is weakly pancylic. At the same time, he conjectured the assertion holds in the condition, ofe(G)>[n2/]-n+ 5. In 1999,Bollobas and Thomason showed that an n-vertexnon-bipartite graph of size at least e(G)>[n2/4]-n + 59 is weakly pancyclic .In this paper, we almost prove the conjecture by establishing the following result: let G be a non-bipartite graph of order n with at least e (G) > [n2/4]-n +12 edges, then G is weakly pancyclic.
|