收缩圈不影响图的hamiltonican index

On Stability of the Hamiltonian Index under Contractions of the Cycle

图G的hamiltonian index是指使G的k次迭线图Lk(G)成为哈密顿图的最小整数k.Xiong Li Ming等在[3]和[4]证明了无论是收缩由图G中度数大于等于3的点所生成的图的所有非平凡分支还是收缩图G的AG(F)-contractible子图F都不会影响图G的hamiltonian index.证明了:图G收缩满足一定条件的圈也不会改变它的hamiltonian index.

The Hamiltonian index of a graph G is the smallest integer k such that the k-th iterated line graph of G is Hamiltonian.Xiong Liming et al[3]and[4]prove that neither the contraction of all nontrivial components of G[{v∶d_G(v)3}] nor the contraction of an A_G(F)-contractible subgraph F affacts the value of the Hamiltonian index of a graph.In this paper,we show that the contraction of a cycle of a graph G which satisfies some conditions also doesnot affets its Hamiltonian index.