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: