On the Steiner Number of the Composition of Graphs

Abstract

Given a connected graph G and a non-empty subset W of V(G), a Steiner W-tree is a tree of minimum order that contains all of W. Let S(W) denote the set of all vertices of G that lie on any Steiner W-tree. If S(W) = V(G), then W is said to be a Steiner set- of G. The Steiner number st (G) of G is defined as the minimum cardinality of a Steiner set of G. In this paper, we characterize the Steiner sets disconnected in the composition G[H] of a non-trivial connected graph G and a disconnected graph H. We then present a formula that can be used to determine the Steiner number st(G[H]).