New sufficient conditions for Hamiltonian, pancyclic and edge-Hamilton graphs.

The decycling number ▽ (G) of a graph G is the smallest number of vertices whose deletion yields a forest. Bau and Beineke proved that κ(G) ≤ ▽(G) + 1 for every graph G, where κ(G) is the connectivity of G (Australas J Combin, 25:285-298, 2002). In this paper, we consider graphs with κ(G) = ▽(G)+1 and establish sufficient conditions for such graphs to be Hamiltonian, pancyclic and edge-Hamilton, respectively. To our knowledge, this is the first result studying Hamilton problem in terms of decycling number. It is well-known that determining the decycling number of a graph is equivalent to finding the greatest order of an induced forest and some sufficient conditions for Hamiltonian graphs are also sufficient for the existence of completely independent spanning trees. This paper may provide a new condition implying completely independent spanning trees. [ABSTRACT FROM AUTHOR]