A vertex traversal of a graph is a sequence of open and close operations applied to the verticies of the graph subject to the following constraints. Any vertex may be opened initially. Thereafter, only a vertex which is adjacent to a currently open vertex may be opened. A vertex may be closed at any time but may never be reopened. A shift operation which simultaneously closes one vertex and opens an adjacent vertex is also allowed. The traversal is complete when all vertices have been opened and closed. The depth of a traversal is the maximum number of verticies open at any moment during the traversal. The depth of a vertex is the minimum depth of any traversal startingat that vertex. A vertex of minnimum depth is called an optimal vertex.

We show the following: the problem of computing the depth of a vertex in an arbitrary graph is NP-complete; the depths of any two vertices in a tree differ by at most one; and an algorithm can be constructed for finding an optimal vertex in a treee and its depth, which is linear in the number of vertices in the tree. We also characterize the locations of optimal vertices in a tree.