Для каких графиков дерево DFS всегда является путем?

Для каких неориентированных графов все деревья поиска в глубину (для всех возможных начальных вершин и для всех вариантов выбора соседей для поиска в первую очередь) являются направленными путями? То есть каждое дерево DFS должно иметь только один лист, а каждая другая вершина должна иметь ровно один дочерний элемент.

Например, это верно для циклов, полных графов и сбалансированных полных двудольных графов.

Найти дерево DFS, которое не является путем, очевидно, в NP. Это NP-полный или полином?

Это эквивалентно тому, что вы можете построить гамильтонов путь, жадно взяв произвольное ребро в каждой вершине. В поисках жадного гамильтонова пути выяснилось: жадно строит гамильтоновы пути, гамильтоновы циклы и максимальные линейные леса , Танкуса и Тарсиб, doi: 10.1016 / j.disc.2006.09.031 , что указывает на случайно прослеживаемые графы , Чартранд и Кронк, SIAM J. Appl. Math., 16 (4), 696–700, doi: 10.1137 / 0116056, характеризующие эти графики как точные графики, упомянутые вами в вопросе.