Forbidden Subgraphs and the Hamiltonian Index of a \(2\)-Connected Graph

Premysl Holub1
1Department of Mathematics, University of West Bohemia, and Institute for Theo- retical Computer Science (ITI), Charles University, Univerzitni 22, 306 14 Pilsen, Czech Republic

Abstract

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.