Pseudo-hamiltonian graphs (Q2714402)

In this paper a pseudo-\(h\)-hamiltonian cycle in a graph is defined as a closed walk that visits every vertex exactly \(h\) times. The pseudo-hamiltonicity number ph(\(G\)) of the graph \(G\), is the smallest integer \(h\geq 1\) for which \(G\) is pseudo-\(h\)-hamiltonian; in case no such \(h\) exists, ph(\(G\))=\(\infty \). It is proved that for each fixed value of \(h\geq 1\), the problem of deciding whether ph(\(G)\leq h\) holds for a given graph \(G\) is NP-complete, but deciding whether there exists an \(h\geq 1\) such that the graph is pseudo-\(h\)-hamiltonian, can be done in polynomial time. This polynomial time result is based on the close relationship of pseudo-hamiltonian graphs with regularizable graphs. Some sufficient conditions for pseudo-\(h\)-hamiltonicity that are based on stable sets and on toughness are also presented. It is shown that the square of a connected graph is always pseudo-hamiltonian. For \(d\)-regular graphs with \(d\geq 3\), there exists a threshold \(\tau (d)\) such that for \(h<\tau (d)\), it is NP-complete to decide whether a \(d\)-regular graph is pseudo-\(h\)-hamiltonian, whereas for every \(h\geq \tau (d)\), a \(d\)-regular graph is always pseudo-\(h\)-hamiltonian. Finally, the computational complexity of computing ph(\(G\)) on many well-known special graph classes is investigated: To decide whether a graph is pseudo-\(h\)-hamiltonian is NP-complete for bipartite, planar, or split graphs, but this can be done in linear time for partial \(k\)-trees and in polynomial time for cocomparability graphs.