On Toughness And Hamiltonicity Of K-split Graphs And C_p~*-graphs

The toughness is one of the important parameter of graphs, there are many results about the toughness since Chvatal put it out in 1973. But there are still many famous apen conjectures that have not been resolved, one of them:for any graph G, is there a Gnite constant to such that every to-tough graph contains a hamilton cycle. In which the relation between toughness and hamiltonian is one of the most hottest issues.We usually use some properties or parameters to identify the conditions for Hamil-tonian when study the hamiltonian of a graph. In this paper, we study the relation between toughness and hamiltonian and use toughness to characterize the hamiltonian of wo special graph classes.The toughness of a non-complete graph G is the minimum value t for which there is a vertex cut S whose removal yields |S|/t components. Determining toughness is an NP-hard problem for general input graph. For k> 2, a graph is called k-split graph if its vertex set can be partitioned into an independent set I and a set C that induces a complete k-partite subgraph with G[C]. In special, if G[C] is a complete subgraph, the graph is denoted split graph. Woeginger et al. prove that the toughness of a split graph can be computed in polynomial time.For an integer p≥3, a Cp*-graph is a graph consisting of p nonempty disjoint inde-pendent sets A1,A2,..., Ap and for all i= 1,2,..., p-1, the sets Ai and Ai+1 induce a complete bipartite graph in C*, just as the sets Ap and A1. Broersma et al. prove that C5*-graph is hamiltonian if and only if it is 1-tough.In this article, first the similar like the split graph we prove that the toughness of k-split graphs can be determined in polynomial time. Then we also prove that every k-tough k-split graph on at least three vertices is hamiltonian. Last, we extend the result of Broersma et al. and prove that the C*-graph is hamiltonian if and only if it is 1-tough (p≥3).