Hamiltonian powers in threshold and arborescent comparability graphs (Q1301703): Difference between revisions

The \(k\)th power of a graph \(H\) is the graph \(H^k\) with vertex set \(V(H^k)= V(H)\), in which distinct vertices \(x\) and \(y\) are adjacent if and only if there is a path of length at most \(k\) between \(x\) and \(y\) in \(H\). Some necessary and sufficient conditions for special classes of graphs to contain powers of Hamiltonian paths and cycles are studied. In particular, some necessary and sufficient conditions for threshold graphs to contain the \(k\)th power of a Hamiltonian cycle are obtained.