TY - JOUR

T1 - Steiner centers and Steiner medians of graphs

AU - Yeh, Hong Gwa

AU - Chiang, Chun Ying

AU - Peng, Sheng Hueng

PY - 2008/11/28

Y1 - 2008/11/28

N2 - Let G be a connected graph and S a set of vertices of G. The Steiner distance of S is the smallest number of edges in a connected subgraph of G that contains S and is denoted by dG (S) or d (S). The Steiner n-eccentricity en (v) and Steiner n-distance dn (v) of a vertex v in G are defined as en (v) = max { d (S) |S ⊆ V (G), | S | = n and v ∈ S } and dn (v) = ∑ { d (S) |S ⊆ V (G), | S | = n and v ∈ S }, respectively. The Steiner n-center Cn (G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n-median Mn (G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Let T be a tree. Oellermann and Tian [O.R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585-597] showed that Cn (T) is contained in Cn + 1 (T) for all n ≥ 2. Beineke et al. [L.W. Beineke, O.R. Oellermann, R.E. Pippert, On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249-258] showed that Mn (T) is contained in Mn + 1 (T) for all n ≥ 2. Then, Oellermann [O.R. Oellermann, On Steiner centers and Steiner medians of graphs, Networks 34 (1999) 258-263] asked whether these containment relationships hold for general graphs. In this note we show that for every n ≥ 2 there is an infinite family of block graphs G for which Cn (G) ⊈ Cn + 1 (G). We also show that for each n ≥ 2 there is a distance-hereditary graph G such that Mn (G) ⊈ Mn + 1 (G). Despite these negative examples, we prove that if G is a block graph then Mn (G) is contained in Mn + 1 (G) for all n ≥ 2. Further, a linear time algorithm for finding the Steiner n-median of a block graph is presented and an efficient algorithm for finding the Steiner n-distances of all vertices in a block graph is described.

AB - Let G be a connected graph and S a set of vertices of G. The Steiner distance of S is the smallest number of edges in a connected subgraph of G that contains S and is denoted by dG (S) or d (S). The Steiner n-eccentricity en (v) and Steiner n-distance dn (v) of a vertex v in G are defined as en (v) = max { d (S) |S ⊆ V (G), | S | = n and v ∈ S } and dn (v) = ∑ { d (S) |S ⊆ V (G), | S | = n and v ∈ S }, respectively. The Steiner n-center Cn (G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n-median Mn (G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Let T be a tree. Oellermann and Tian [O.R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585-597] showed that Cn (T) is contained in Cn + 1 (T) for all n ≥ 2. Beineke et al. [L.W. Beineke, O.R. Oellermann, R.E. Pippert, On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249-258] showed that Mn (T) is contained in Mn + 1 (T) for all n ≥ 2. Then, Oellermann [O.R. Oellermann, On Steiner centers and Steiner medians of graphs, Networks 34 (1999) 258-263] asked whether these containment relationships hold for general graphs. In this note we show that for every n ≥ 2 there is an infinite family of block graphs G for which Cn (G) ⊈ Cn + 1 (G). We also show that for each n ≥ 2 there is a distance-hereditary graph G such that Mn (G) ⊈ Mn + 1 (G). Despite these negative examples, we prove that if G is a block graph then Mn (G) is contained in Mn + 1 (G) for all n ≥ 2. Further, a linear time algorithm for finding the Steiner n-median of a block graph is presented and an efficient algorithm for finding the Steiner n-distances of all vertices in a block graph is described.

KW - Block graph

KW - Steiner center

KW - Steiner distance

KW - Steiner median

KW - Steiner n-distance

KW - Steiner n-eccentricity

UR - http://www.scopus.com/inward/record.url?scp=50649092023&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2007.08.094

DO - 10.1016/j.disc.2007.08.094

M3 - 期刊論文

AN - SCOPUS:50649092023

SN - 0012-365X

VL - 308

SP - 5298

EP - 5307

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 22

ER -