The edge Steiner number of a graph

Abstract

For a non-trivial connected graph G of order p, a set W⊆V(G) is called an edge Steiner set of G if every edge of G is contained in a Steiner W-tree of G. The edge Steiner number s ₁ (G) of G is the minimum cardinality of its edge Steiner sets and any edge Steiner set of cardinality s ₁ (G) is a minimum edge Steiner set of G. Connected graphs with edge Steiner number 2 are characterized. Various necessary conditions for the edge Steiner number of a graph to be p–1 or p are given. It is shown that every pair k, p of integers with 2≤k≤p is realizable as the edge Steiner number and order of some connected graph. For positive integers r, d and k≥2 with r<d≤2r, there exists a connected graph of radius r, diameter d and edge Steiner number k. It is shown that s(G)≤s ₁ (G), where s(G) is the Steiner number of G. It is also shown that for every two integers a and b such that 2≤a≤b, there exists a connected graph G with s(G)=a and s ₁ (G)=b. An edge Steiner set W, no proper subset of which is an edge Steiner set, is a minimal edge Steiner set. The upper edge Steiner number of a graph G is the maximum cardinality of a minimal edge Steiner set of G. It is shown that for every two integers a and b such that 2≤a≤b, there exists a connected graph G with s ₁ (G)=a and .

Keywords:

• Geodetic number
• edge geodetic number
• Steiner distance
• Steiner number
• edge Steiner set
• edge Steiner number