Finding a Hamiltonian path in this graph family

Question

Given a directed graph $G = (V, E)$, you have been told that a Hamiltonian path $p_0p_1\ldots p_V$ exists with the property that for each edge $p_ip_j$ that is not part of the Hamiltonian path, $i > j$.

Find any Hamiltonian path.

It is not too hard to find an $O(|V||E|)$ solution to this problem: for every vertex with out-degree one, try starting a BFS from this vertex. If ever there is more than one vertex that could be expanded next in the BFS, give up and try another vertex.

I am not necessarily looking for a more efficient solution than this (though that would be nice), but I'm having trouble finding literature on this type of graph (in general, it seems very hard to look up literature on a family of graphs you do not know the name of).

Do you know where I can find out more about this graph family, or other graph families that involve guaranteeing the existence of a Hamiltonian path/cycle with interesting properties?

Answer 1

The class of graphs that contain a Hamiltonian cycle is known as Hamiltonian graphs. Being Hamiltonian doesn't really imply much: a wide range of well-known graph parameters (diameter, treewidth, chromatic number, ...) can still be unbounded. At least partly, this is the reason there aren't many non-trivial subclasses of Hamiltonian graphs known.

As an example, every 2-connected $(P_6,K_{1,3})$-free graph is Hamiltonian (see e.g., [1]). Further, [1] also cites some conjectures which claim that every 2-tough graph is Hamiltonian, or that every 4-connected $K_{1,3}$-free graph is Hamiltonian.

On the algorithmic side, even recognizing Hamiltonian graphs is of course well-known to be NP-complete. That is, recognition means the problem of deciding whether a given graph is Hamiltonian or not. Also, because many structural parameters remain unbounded, many classical problems also remain hard for Hamiltonian graphs (as there is no clear algorithmic foothold to exploit).

You might also enjoy Hypohamiltonian graphs, which are "almost Hamiltonian".

---

[1] R. Faudree, E. Flandrin, Z. Ryjacek. Claw-free graphs - a survey. Discrete Math. 164 87-147 (1997)

Answer 2

"I'm having trouble finding literature on this type of graph"

A good book recommended by universities is Discrete Mathematics and It's Applications by Kenneth H. Rosen. You can find the chapter on graphs (Euler and Hamilton paths) on page 666.