Technical Report CS0519

Title: Hamiltonian and Degree Restricted DFS Trees
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 tree" that may be used subsequently.

In some problems the degree of some vertices in the DFS tree obtained in a certain run are crucial and therefore we consider the following problem: Let G=(V,E) be a connected undirected graph where |V|=n and let d from N^n be a degree sequence upper bound vector. Is there any DFS tree T with degree sequence dT that violates d,(i.e. dT<=d which means: exists j such that dT(j) > dT(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. d=(n-l,...,n-l,k,n-l,...,n-l)). However, for the special interesting case where d=(2,2,...,2), which means that the underline graph of every DFS tree is an Hamiltonian path, a complete characterization of all graphs that support this restriction is given. The main 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 Kn or a Kn,n. This characterization enables us to recognize such graphs by efficient and simple sequential and parallel algorithins.

Key words: DFS trees, complete characterization, degree restricted, graph algorithms, Hamiltonian path, NP-Complete, parallel algorithms.

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 1988
To the main CS technical reports page

Computer science department, Technion