On s‐Hamiltonian Line Graphs
Hong‐Jian Lai, Yehong Shao · Journal of Graph Theory · 2013
Abstract For an integer s ≥ 0, a graph G is s‐hamiltonian if for any vertex subset with |S′| ≤ s, G ‐ S′ is hamiltonian. It is well known that if a graph G is s‐hamiltonian, then G must be (s+2)‐connected. The converse is not true, as there exist arbitrarily highly connected nonhamiltonian graphs. But for line graphs, we prove that when s ≥ 5, a line graph is s‐hamiltonian if and only if it is (s+2)‐connected.