Für welche Diagramme ist der DFS-Baum immer ein Pfad?

Für welche ungerichteten Graphen gibt es alle Tiefensuchbäume (für alle möglichen Startscheitelpunkte und für alle Auswahlmöglichkeiten, nach welchen Nachbarn zuerst gesucht werden soll) gerichtete Pfade? Das heißt, jeder DFS-Baum sollte nur ein Blatt haben, und jeder andere Scheitelpunkt sollte genau ein Kind haben.

Dies gilt beispielsweise für Zyklen, vollständige Diagramme und ausgeglichene vollständige zweiteilige Diagramme.

Einen DFS-Baum zu finden, der kein Pfad ist, liegt offensichtlich in NP. Ist es NP-vollständig oder polynomisch?

Dies entspricht der Eigenschaft, dass Sie einen Hamilton-Pfad konstruieren können, indem Sie an jedem Scheitelpunkt gierig eine beliebige Kante nehmen. Auf der Suche nach gierigen Hamilton- Pfaden sind aufgetaucht : Gierig konstruierte Hamilton-Pfade, Hamilton-Zyklen und maximale lineare Wälder , Tankusa und Tarsib, doi: 10.1016 / j.disc.2006.09.031 , die auf nach dem Zufallsprinzip nachvollziehbare Graphen verweisen , Chartrand und Kronk, SIAM J. Appl. Math., 16 (4), 696–700, doi: 10.1137 / 0116056 , um diese Diagramme als genau die Diagramme zu kennzeichnen, die Sie in der Frage erwähnen.