## Abstract

Let G be a graph other than a path. The m-iterated line graph of a graph G is L^{m}(G)=L(L^{m−1}(G)). where L^{1}(G) denotes the line graph L(G) of G. Define the Hamiltonian index h(G) of G to be the smallest integer m such that L^{m}(G) contains a Hamiltonian cycle. For a connected graph set H, G is said to be H-free if G does not contain H as an induced subgraph for all H∈H. In this paper, we characterize all forbidden graphs H for any integer k≥2 and partial forbidden graphs H for k=1 such that a connected (or 2-edge-connected or 2-connected) H-free graph G satisfies that h(G)≤k for the case when |H|≤2. What is more, we settle four conjectures proposed in Holub (2014).

Original language | English |
---|---|

Article number | 111841 |

Journal | Discrete Mathematics |

Volume | 343 |

Issue number | 6 |

DOIs | |

Publication status | Published - Jun 2020 |

## Keywords

- Collapsible
- DCT
- Forbidden subgraph
- Hamiltonian index