The Upper Edge Fixed Steiner Number of a Graph

Abstract

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 subgraph of G containing W. Necessarily, each such subgraph is a tree and is called a Steiner tree with respect to W or a Steiner W-tree. $S(W)$ denotes the set of vertices that lies in Steiner W-trees. Let G be a connected graph with at least 2 vertices. A set $W \subseteq V(G)$ is called a Steiner set of G if $S(W) = V(G)$. The Steiner number $s(G)$ is the minimum cardinality of a Steiner set. Let G be a connected graph with at least 3 vertices. For an edge $e = xy$ in G, a set $W \subseteq V(G) -\{x, y\}$ is called an edge fixed Steiner set of G if $W' = W \cup \{x, y\}$ is a Steiner set of G. The minimum cardinality of an edge fixed Steiner set is called the edge fixed Steiner number of G and is denoted by $s_e (G)$. Also the Steiner W-tree necessarily contains the edge e and is called edge fixed Steiner W-tree. In this paper, the concept of upper edge fixed Steiner number of a graph G denoted by $s_e^+(G)$ is studied. Also the graphs in which the upper edge fixed Steiner number is equal to n or $n-1$ are characterized. It is shown that for every pair a, b of integers with $a \geq 3$ and $b \geq 3$, there exists a connected graph G with $s_e(G) = a$ and $s_e^{+}(G)= b$.