Forbidden subgraphs and the hamiltonian index of a 2-connected graph

摘要

Hamiltonian index of a graph G is the smallest positive integer k, for which the k-th iterated line graph L-k(G) is hamiltonian. Bedrossian characterized all pairs of forbidden induced subgraphs that imply hamiltonicity in 2-connected graphs. In this paper, some upper bounds on the hamiltonian index of a 2-connected graph in terms of forbidden not necessarily induced subgraphs are presented.