Extreme Edge Fixed Steiner Graphs

For a non-empty set W of vertices in a connected graph G, the Steiner distance d(W) of W is the minimum size of a connected sub graph of G containing W. S(W ) denotes the set of vertices that lies in Steiner W-trees. Steiner sets and Steiner number of a graph G was studied in [3]. A vertex v is an extreme vertex of a graph G if the sub graph induced by its neighbours is complete. The number of extreme vertices in G is its extreme order Ext(G). Extreme Steiner graphs were introduced and studied in [7]. Edge fixed Steiner sets of a graph G and the edge fixed Steiner number of G were introduced and characterized in [6]. In this paper we introduce an extreme edge fixed Steiner graph and a perfect extreme edge fixed Steiner graph. Some standard graphs are analyzed and characterized as extreme edge fixed Steiner graphs and perfect extreme edge fixed Steiner graphs. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with Ext(G) = a and se(G) = b for some edge e in G.