Steiner centers and Steiner medians of graphs
| Autor: | Sheng-Hueng Peng, Chun-Ying Chiang, Hong-Gwa Yeh |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Block graph
Discrete mathematics Steiner center Efficient algorithm Steiner n-distance Steiner distance Vertex connectivity Graph theory Steiner median Graph Theoretical Computer Science Vertex (geometry) Combinatorics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Discrete Mathematics and Combinatorics Steiner n-eccentricity Time complexity Connectivity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Mathematics. 308:5298-5307 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2007.08.094 |
| Popis: | 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 d"G(S) or d(S). The Steiner n-eccentricity e"n(v) and Steiner n-distance d"n(v) of a vertex v in G are defined as e"n(v)=max{d(S)|[email protected]?V(G), |S|=n and [email protected]?S} and d"n(v)[email protected]?{d(S)|[email protected]?V(G), |S|=n and [email protected]?S}, respectively. The Steiner n-center C"n(G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n-median M"n(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 C"n(T) is contained in C"n"+"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 M"n(T) is contained in M"n"+"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 C"n(G)@?C"n"+"1(G). We also show that for each n>=2 there is a distance-hereditary graph G such that M"n(G)@?M"n"+"1(G). Despite these negative examples, we prove that if G is a block graph then M"n(G) is contained in M"n"+"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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect