Steiner centers and Steiner medians of graphs (Q2519846): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2007.08.094 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1994891352 / rank | |||
Normal rank |
Revision as of 22:47, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Steiner centers and Steiner medians of graphs |
scientific article |
Statements
Steiner centers and Steiner medians of graphs (English)
0 references
27 January 2009
0 references
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.
0 references
Steiner center
0 references
Steiner median
0 references
block graph
0 references
Steiner distance
0 references
Steiner \(n\)-eccentricity
0 references
Steiner \(n\)-distance
0 references