Technical Report Number
We relate two concepts in graph theory and algorithmic complexity, namely the search number and the vertex separation of a graph. Lengauer has previously related vertex separation to progressive black/white pebble demand. Let a (G) denote the search number and vs(G) denote the vertex separation of a connected, undirected graph G. We show that vs(G) < s(G) < vs(G) +2 and we give a simple transformation from G to G^1 such that vs(G^1) = s(G). We give algorithm that, for any tree T, compute vs(T) in linear time and compute an optimal layout with respect to vertex separation in time O(n log n). We characterize those trees having a given vertex separation and describe the smallest such trees. We give an algorithm which, for all fixed k>1, decides the problem: "Is vs(G)
Ellis, J. A.; Sudborough, H.; and Turner, Jonathan S., "Graph Separation and Search Number" Report Number: WUCS-87-11 (1987). All Computer Science and Engineering Research.