Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

• Published in: Discrete mathematics 2007-01, Vol.307 (1), p.88-96
• Main Authors: Oellermann, Ortrud R., Puertas, María Luz
• Format: Article
• Language: English
• Subjects: Combinatorics; Combinatorics. Ordered structures; Contour vertices; Convex and discrete geometry; Distance-hereditary graph; Exact sciences and technology; Geodetic number; Geometry; Graph theory; Mathematics; Sciences and techniques of general use; Steiner geodetic number; Steiner geodetic set; Steiner interval
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2006.04.037

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 ) = I [ u , 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 ∈ S I [ u , 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.