Technical Report CS0612

Authors: E. Korach and Z. Ostfeld
Abstract: The Depth First Search (DFS) algorithm is one of the basic techniques which is used in a very large variety of graph algorithms. Every application of the DFS involves, beside traversing the graph, constructing a special structured tree, called a DFS tref;. In this paper, 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 tenns of forbidden minors and forbidden topological minors. The complete characterization implies explicit linear algorithm 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 4 e N^n be a degree sequence upper bound vector. Is there any DFS tree T with degree sequence 4T that violates f!, (i.e. 4T $f! which means: 3 j such that f!TCj) > ~j? We show that this problem is NP -Complete even for the case where we restrict the degree of only one specific vertex to be less than or equal to k for a fixed k~2 (i.e. f! =(n-l,..., n-l, k, n-l,..., n-l. However, for the special interesting case where f! =(2,2,...,2), which means that the underlying graph of every DFS tree is an Hamiltonian path, a complete characterization of all graphs that support this restriction is given. The theorem which implies this characterization is the following: G is an undirected graph in which every DFS tree is a directed Hamiltonian path if and only if G is one of the following graphs: a simple circuit, a K" or a K",,,. This characterization implies efficient recognition algorithm for these graphs.

Key words: DFS trees, complete characterization, degree restricted, graph algorithms, graph minors, Hamiltonian path, NP-Complete. AMS(MOS) subject classification: 05C05, 05C38, 05C45, 05C75, 68Q25, 68R10

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion