Steiner centers and Steiner medians of graphs (Q2519846): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
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 | |||
Property / cites work | |||
Property / cites work: On the Steiner median of a tree / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Steiner distance in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Steiner Distance-Hereditary Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4934868 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Steiner centers in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Depth-First Search and Linear Graph Algorithms / rank | |||
Normal rank |
Latest revision as of 00:59, 29 June 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