Powers of connected graphs and hamiltonicity
A graph G is n-hamiltonian (resp. n-edge hamiltonian) if after the removal of any k vertices (resp. edges) with 0\(\leq k\leq n\), the resulting graph is hamiltonian. The kth power of a graph G is the graph having the same vertex-set as G and such that u and v, vertices of \(G^ k\), are adjacent if and only if the distance between u and v in G is at most k. In this paper the authors prove that if G is a connected graph then \(G^ k\) is (k-2)-edge hamiltonian if \(k\geq 3\) and \(| V(G)|\geq k+1.\) Furthermore, if G is 2-connected and \(| V(G)\geq k+2\) then \(G^ k\) is (k-1)-edge hamiltonian.
scientific article; zbMATH DE number 3871404