Graph Separation and Search Number
John A. Ellis · Open Scholarship Institutional Repository (Washington University in St. Louis) · 1987
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) 1, decides the problem: "Is vs(G)