Randomly Near-Traceable Graphs
John Frederick Fink · SIAM Journal on Algebraic and Discrete Methods · 1985
A walk generated by a (not necessarily completed) depth-first search of a graph is called a DFS walk. A connected graph is randomly near-traceable if it admits no DFS walk $W:w_1 ,w_2 , \cdots ,w_n $ having consecutive vertices $w_k $ and $w_{k + 1}$ that both appear on the subwalk $w_1 ,w_2 , \cdots ,w_{k - 1} $; thus, in a depth-first search of a randomly near-traceable graph, whenever we backtrack to a previously visited vertex, that vertex is adjacent to at least one unvisited vertex. We characterize the bipartite randomly near-traceable graphs and show that for every randomly near-traceable graph G that is not a cycle, the radius of G is at most 2. Other results are also presented.