id: 00786113 dt: j an: 00786113 au: Korach, Ephraim; Ostfeld, Zvi ti: On the existence of special depth first search trees. so: J. Graph Theory 19, No.4, 535-547 (1995). py: 1995 pu: John Wiley \& Sons, New York, NY la: EN cc: ut: graph algorithms; complete characterization; spanning tree; minors; recognition; linear algorithm; degree sequence; NP-complete ci: li: doi:10.1002/jgt.3190190408 ab: Summary: The Depth First Search (DFS) algorithm is one of the basic techniques that is used in a very large variety of graph algorithms. Most applications of the DFS involve the construction of a depth-first spanning tree (DFS tree). We give a complete characterization of all the graphs in which every spanning tree is a DFS tree. These graphs are called Total-DFS-Graphs. We prove that Total-DFS-Graphs are closed under minors. It follows by the work of Robertson and Seymour on graph minors that there is a finite set of forbidden minors of these graphs and that there is a polynomial algorithm for their recognition. We also provide explicit characterizations of these graphs in terms of forbidden minors and forbidden topological minors. The complete characterization implies explicit linear algorithms for their recognition. In some problems the degree of some vertices in the DFS tree obtained in a certain run are crucial and therefore we also consider the following problem: Let $G= (V, E)$ be a connected undirected graph where $|V|= n$ and let ${\bold d}\in {\bbfN}^n$ be a degree sequence upper bound vector. Is there any DFS tree $T$ with degree sequence ${\bold d}_T$ that violates ${\bold d}$ (i.e., ${\bold d}_T\not\leq {\bold d}$, which means: there exists $j$ such that ${\bold d}_T(j)> {\bold d}(j)$)? We show that this problem is NP-complete even for the case where we restrict the degree of only on specific vertex to be less than or equal to $k$ for a fixed $k\ge 2$ (i.e., ${\bold d}= (n- 1,\dots, n- 1, k, n- 1,\dots, n- 1)$). rv: