# Finding a Hamiltonian path in this graph family

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?

As an example, every 2-connected $$(P_6,K_{1,3})$$-free graph is Hamiltonian (see e.g., ). Further,  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.