Several Sufficient Conditions For Hamiltonian Graphs

Let G be a graph. A graph is hamiltonian if it contains a hamilton cycle.Assume that integer k 1. A nonnegative rational sequence ( 1, 2,... , k+1) is called H-sequence if the following conditions are satisfied[11]:(1). l 1;(2). For arbitrary i1, i2, ... ,ih implies In this paper, by using the vertex inserting lemmas and the concept of H-sequence[11], we provide some new sufficient conditions for hamiltonian graphs, which are related to the independent sets or the essential independent sets.Theorem 1 Let G be a simple graph which has n vertices, . In addition ( ) is an H-sequence. Iffor each Y Ik+1(G), then G is hamiltonian.Above Theorem 1 is the deduction of the next Theorem 2. At first when we began to prove the Theorem 2, we met some difficulty in choosing the right Y. But during the process of proving the Theorem 1, we got some inspiration. So we finished the proof of Theorem 2 in the end. For this reason we give the proofs of Theorem 1 and Theorem 2 at the same time in this paper.Theorem 2 Let G be a simple graph which has n vertices, 2. In addition( 1, 2, ... , k+1) is an H-sequence. Iffor each Y I(e)k+1(G), then G is hamiltonian.In addition the author discussed with her classmate Chen Lijuan in second writer. In the end we got the following theorem.Theorem 3 Let G be a simple graph which has n vertices, k is any positive integer with k n.(1) If the degree sum of any pair of nonadjacent vertices is at least n-k,G can be partitioned into k subgraphs Hi which Hi is a cycle or a path(1 i k).(2) If the maximum degree of any pair of nonadjacent vertices is at least , then G can be partitioned into k subgraphs Hi which Hi is a cycle or a path(1 i k).