On the Steiner, geodetic and hull numbers of graphs (Q1779492)

A Steiner set of a graph \(G\) is a subset \(W\) of \(V(G)\) such that all vertices of \(G\) lie on some tree of minimum order that contains all vertices of \(W\). The minimum order of a Steiner set of \(G\) is called the Steiner number of \(G\). Let \(I[u,v]\) and \(J[u,v]\) denote the set of all vertices in \(G\) lying on some \(u\)-\(v\) geodesic and on some induced \(u\)-\(v\) path, respectively. Given a set \(S\subseteq V(G)\), \(I[S]\) and \(J[S]\) denote the geodetic closure and the monophonic closure of \(S\), i.e., the union of all \(I[u,v]\) and \(J[u,v]\), respectively, over all \(u,v\in S\). If \(I[S]\) and \(J[S]\), respectively equals \(V(G)\), then \(S\) is called a geodetic and a monophonic set, respectively. The geodetic number of \(G\) is equal to the minimum order of a geodetic set in \(G\). In this paper relationships between Steiner sets and geodetic sets and between Steiner sets and monophonic sets are studied. It is shown, e.g., that every Steiner set in a connected graph must also be monophonic, and that every Steiner set in a connected interval graph must be geodetic. The authors prove that there exists a connected graph having prescribed pairs of hull, geodetic or Steiner numbers satisfying some inequalities.