Pour quels graphiques l'arbre DFS est-il toujours un chemin?

Pour quels graphiques non orientés tous les arbres de recherche en profondeur d'abord (pour tous les sommets de départ possibles et pour tous les choix des voisins à rechercher en premier) sont-ils des chemins dirigés? C'est-à-dire que chaque arbre DFS ne doit avoir qu'une seule feuille et que chaque autre sommet doit avoir exactement un enfant.

Par exemple, c'est vrai pour les cycles, les graphiques complets et les graphiques bipartites complets équilibrés.

Trouver un arbre DFS qui n'est pas un chemin est évidemment dans NP. Est-il NP-complet ou polynomial?

Cela équivaut à la propriété que vous pouvez construire un chemin hamiltonien en prenant avidement un bord arbitraire à chaque sommet. La recherche d'un chemin hamiltonien gourmand est apparue : Construire avec gourmandise des chemins hamiltoniens, des cycles hamiltoniens et des forêts linéaires maximales , Tankusa et Tarsib, doi: 10.1016 / j.disc.2006.09.031 , qui pointe vers Randomly Traceable Graphs , Chartrand et Kronk, SIAM J. Appl. Math., 16 (4), 696–700, doi: 10.1137 / 0116056 comme caractérisant ces graphiques comme étant précisément les graphiques que vous mentionnez dans la question.