The Hamilton-Connectedness Of Claw-Free Graphs And Its Application

The problem on hamilton-connectedness of graphs is a very important problem in graph theory and the research is very active. A hamiltonian path is a path that visits each vertex exactly once. G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices. Hamilton-connectedness is one of the most important characteristic of Internet. Hamilton-connectedness of the network means there exists at least one hamiltonian path between any two distinct vertices. When the network is broadcasting data, it can effectively avoid communication delay caused by some serious link block.In this paper we consider a special and important class of claw-free graphs. A graph is claw-free if it contains no induced subgraph isomorphic to K_1,3, where K_1,3 is a complete bipartite graph. A vertex of a graph is locally connected if its neighborhood is connected. A graph G is locally connected if every vertex of G is locally connected.In this paper, we get the following results:(1) Let G be a 3-connected K_1,3 -free graph of order n. If n≤6δ-10 and d_P (H)=4, then G is hamiltonian connected.(2) Every 4-connected, 4-regular, locally connected K_1,3 -free graph G of order n≥5 is hamiltonian connected.(3) We provide a constructive characterization of 4-connected 4-regular locally connected claw-free graphs.(4) We give an application of 4-connected, 4-regular, locally connected K_1,3 -free graphs in application-layer multicasting.