# Technical Report CS0519

 TR#: CS0519 Class: CS Title: Hamiltonian and Degree Restricted DFS Trees Authors: E. Korach and Z. Ostfeld PDF CS0519.pdf 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. Copyright The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1988/CS/CS0519), rather than to the URL of the PDF files directly. The latter URLs may change without notice.