Dla których wykresów drzewo DFS jest zawsze ścieżką?

Dla których niekierowanych wykresów są wszystkie drzewa pierwszego wyszukiwania głębokości (dla wszystkich możliwych wierzchołków początkowych i dla wszystkich wyborów, których sąsiadów najpierw szukać) ścieżki skierowane? Oznacza to, że każde drzewo DFS powinno mieć tylko jeden liść, a każdy inny wierzchołek powinien mieć dokładnie jedno dziecko.

Dotyczy to na przykład cykli, kompletnych wykresów i zrównoważonych kompletnych wykresów dwustronnych.

Znalezienie drzewa DFS, które nie jest ścieżką, jest oczywiście w NP. Czy jest to NP-zupełne czy wielomianowe?

Jest to równoważne z właściwością, którą można zbudować ścieżką hamiltonowską, łapczywie zdobywając dowolną przewagę na każdym wierzchołku. Pojawiło się poszukiwanie chciwej ścieżki hamiltonowskiej : chciwe budowanie ścieżek hamiltonowskich, cykle hamiltonowskie i maksymalne lasy liniowe , Tankusa i Tarsib, doi: 10.1016 / j.disc.2006.09.031 , co wskazuje na losowo wykrywalne wykresy , Chartrand i Kronk, SIAM J. Appl. Math., 16 (4), 696–700, doi: 10.1137 / 0116056 jako charakteryzujące te wykresy jako dokładnie wykresy wspomniane w pytaniu.