{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,3]],"date-time":"2024-03-03T21:26:25Z","timestamp":1709501185014},"reference-count":28,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,6]],"date-time":"2006-10-06T00:00:00Z","timestamp":1160092800000},"content-version":"vor","delay-in-days":4115,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1995,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>Depth First Search<\/jats:italic> (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\u2010first spanning tree (<jats:italic>DFS tree<\/jats:italic>).<\/jats:p><jats:p>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 <jats:italic>Total\u2010DFS\u2010Graphs.<\/jats:italic> We prove that Total\u2010DFS\u2010Graphs 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 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 <jats:italic>G = (V,E<\/jats:italic>) be a connected undirected graph where |V| = <jats:italic>n<\/jats:italic> and let <jats:italic><jats:bold>d<\/jats:bold><\/jats:italic> \u03f5 <jats:italic>N<jats:sup>n<\/jats:sup><\/jats:italic> be a degree sequence upper bound vector. <jats:italic>Is there any DFS tree T with degree sequence<\/jats:italic> <jats:bold>d<\/jats:bold><jats:sub>T<\/jats:sub> <jats:italic>that violates<\/jats:italic> <jats:bold>d<\/jats:bold> (<jats:italic>i.e.<\/jats:italic>, <jats:bold>d<\/jats:bold><jats:sub>T<\/jats:sub> \u2264 <jats:bold>d<\/jats:bold>, <jats:italic>which means<\/jats:italic>: E j <jats:italic>such that<\/jats:italic> <jats:bold>d<\/jats:bold><jats:sub>T<\/jats:sub>(j) &gt; <jats:bold>d<\/jats:bold>(j))? We show that this problem is <jats:italic>NP\u2010complete<\/jats:italic> 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 \u2265 2 (i.e., d = (n \u2010 1, \u20db, n \u2010 1, k, n \u2010 1, \u20db, n \u2010 1)). 0 1995 John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/jgt.3190190408","type":"journal-article","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T15:25:53Z","timestamp":1181229953000},"page":"535-547","source":"Crossref","is-referenced-by-count":2,"title":["On the existence of special depth first search trees"],"prefix":"10.1002","volume":"19","author":[{"given":"Ephraim","family":"Korach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Ostfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,6]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122548"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90083-3"},{"key":"e_1_2_1_4_2","volume-title":"Graph Theory with Applications","author":"Bondy J. A.","year":"1977"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0116056"},{"key":"e_1_2_1_6_2","series-title":"14th International Workshop on Graph\u2010Theoretic Concepts in Computer Science, Amsterdam, Lecture Notes in Computer Science 344","first-page":"30","volume-title":"The monadic second\u2010order logic of graphs: Definable sets of finite graphs","author":"Courcelle B.","year":"1988"},{"key":"e_1_2_1_7_2","first-page":"195","volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B.","year":"1990"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"R.Cole Parallel merge sort.Proc. 27th IEEE Symp. Found. Comput. Sci.(1986) 511\u2010516.","DOI":"10.1109\/SFCS.1986.41"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762131"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44491"},{"key":"e_1_2_1_11_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_12_2","unstructured":"T.HagerupandM.Nowak Recognition of spanning trees defined by graph searches. Technical Report A 85\/08. Universit\u00e4t des Saarlandes Saaarbr\u00fc\u00e4cken West Germany (1985)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362272"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217028"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"E.KorachandZ.Ostfeld DFS tree construction: Algorithms and characterizations. Technical Report No. 515 CS Dept. Technion July (1988). [A preliminary version of this paper can be found in14th International Workshop on Graph\u2010Theoretic Concepts in Computer Science Amsterdam Lecture Notes in Computer Science 344. Springer\u2010Verlag New York (1988) 87\u2010106.]","DOI":"10.1007\/3-540-50728-0_37"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90375-4"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90228-6"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"e_1_2_1_21_2","first-page":"399","volume-title":"Progress in Graph Theory","author":"Robertson N.","year":"1984"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"N.RobertsonandP. D.Seymour Graph minors XIII. The disjoint paths problem. Manuscript (1986).","DOI":"10.1016\/0095-8956(86)90031-6"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215058"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1984.1085460"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90040-4"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.001"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190190408","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190190408","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T19:37:37Z","timestamp":1698262657000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190190408"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["10.1002\/jgt.3190190408"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190190408","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}