Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs |
| |
Authors: | Ortrud R Oellermann María Luz Puertas |
| |
Institution: | a Department of Mathematics and Statistics, The University of Winnipeg, 515 Portage Avenue, Winnipeg, MB, Canada R3B 2E9 b Department of Statistics and Applied Mathematics, University of Almería, 04120, Almería, Spain |
| |
Abstract: | A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=Iu,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?u,v∈SIu,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph. |
| |
Keywords: | primary 05C12 secondary 05C05 52B40 |
本文献已被 ScienceDirect 等数据库收录! |
|