¿Para qué gráficos el árbol DFS es siempre una ruta?

¿Para qué gráficos no dirigidos son todos los árboles de búsqueda de profundidad primero (para todos los vértices iniciales posibles y para todas las opciones de qué vecinos buscar primero) rutas dirigidas? Es decir, cada árbol DFS debe tener solo una hoja, y todos los demás vértices deben tener exactamente un hijo.

Por ejemplo, es cierto para ciclos, gráficos completos y gráficos bipartitos completos equilibrados.

Encontrar un árbol DFS que no es una ruta es obviamente en NP. ¿Es NP completo o polinomial?

Esto es equivalente a la propiedad de que puede construir un camino hamiltoniano tomando con avidez un borde arbitrario en cada vértice. En busca de un codicioso camino hamiltoniano apareció: construyendo con avidez caminos hamiltonianos, ciclos hamiltonianos y bosques lineales máximos , Tankusa y Tarsib, doi: 10.1016 / j.disc.2006.09.031 , que apunta a Gráficos trazables al azar , Chartrand y Kronk, SIAM J. Appl. Math., 16 (4), 696–700, doi: 10.1137 / 0116056 que caracteriza estos gráficos como precisamente los gráficos que menciona en la pregunta.