Steiner's problem in graphs and its implications

Abstract

Abstract A graph theoretic version of Steiner's problem in plane geometry is described. An approach for solving this problem, related to Melzak's solution to Steiner's problem, is presented. The problems of finding “shortest route” and “minimal spanning tree” in graphs become special cases of the Steiner's problem in graphs. It is shown that a solution to this problem also provides us with a solution to the problems of finding a minimum externally stable set and a maximum internally stable set in a graph.