On The Hamiltonian Path Index

The n-iterated line graph Ln(G)of a graph G is defined to be L(Ln-1()),where L1(G)denotes the line graph L(G)of G,and Ln-1(G)is assumed to be nonempty.Harary and Nash-Williams characterized those graphs G for which L(G)is hamiltonian.The hamiltonian index(resp.,hamiltonian path index)of a graph G is the minimum number n such that Ln(G)is hamiltonian(resp.,traceable,i.e.,Ln(G)has a hamiltonian path).Xiong and Liu characterized those graphs G for which Ln(G)is hamiltonian,and Niu et al.characterized those graphs G for which Ln(G)is traceable.They showed several exact values and upper bounds of the hamiltonian index and hamiltonian path index,respectively.In this paper,the hamiltonian index is further studied,and some exact values and upper and lower bounds are given.This thesis consists of four chapters.In Chapter 1,we present the methods of the hamiltonian(path)index,the background of research contents,and some terminologies and notations.In Chapter 2,firstly,on the premise of the hamiltonian index of trees proved by Char-trand and Wall,we prove the hamiltonian path index of trees.Secondly,on the premise of Sarazin proved the hamiltonian index based on cyclic block,the hamiltonian path index based on cyclic block is studied.Finally,on the premise of the hamiltonian index about con-traction proved by Liming Xiong and Zhanhong Niu,a lemma is given to prove hamiltonian path index based on contraction.In Chapter 3,we prove the upper bound of hamiltonian path index of connected graphs on the premise of the existing upper and lower bound of hamiltonian index.The upper bound and lower bound of hamiltonian path index based on split block and branch bonds are also studied.In Chapter 4,we summarize and analyze the main research contents and important conclusions of this paper.