Steiner centers and Steiner medians of graphs (Q2519846): Difference between revisions

Let \(G\) be a connected graph and \(S\) a set of vertices of \(G\). The Steiner distance \(d(S)\) of \(S\) is the smallest number of edges in a connected subgraph of \(G\) that contains \(S\). For a vertex \(v\) and positive integer \(n\), the \(n\)-eccentricity \(e_n(v)\) and \(n\)-distance \(d_n(v)\) of \(v\) are defined as follows: \[ \begin{aligned} e_n(v) &= \max\{d(S)| S \subseteq V(G), |S| = n ~ and ~ v \in S\}\\ \text{and}d_n(v) &= \sum\{d(S)| S \subseteq V(G), |S| = n,~and~ v \in S\}.\end{aligned} \] The \(n\)-centre \(C_n(G)\) is the subgraph induced by the vertices of minimum \(n\)-eccentricity and the \(n\)-median \(M_n(G)\) of \(G\), is the subgraph of \(G\) induced by the vertices with minimum \(n\)-distance. It is known that if \(G\) is a tree, then \(C_n(G) \subseteq C_{n+1}(G)\) and \(M_n(G) \subseteq M_{n+1}(G)\). The authors show that these containments do not hold in general. In particular they show that for every \(n \geq 2\) there is an infinite family of block graphs for which the first containment does not hold and for each \(n \geq 2\) they show that there is a distance-hereditary graph \(G\) such that \(M_n(G) \not\subseteq M_{n+1}(G)\). They show that for a block graph \(G\), \(M_n(G) \subseteq M_{n+1}(G)\) and find an efficient algorithm that determines the \(n\)-distance of every vertex in a block graph.