Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs
type: Item
instance of: scholarly article
title: Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs
zbMATH Open document ID: 1156.05017
author: Linda Eroh
author: Ortrud R. Oellermann
published in: Discrete Mathematics
publication date: 2008-09-04T00:00:00Z
review text: In a connected graph \(G=(V,E)\), a set \(S\subset V\) is a (Steiner) geodetic set if all \(v\in V\) lie on some shortest path between two vertices in \(S\) (resp. some Steiner subtree for \(S\) in \(G\)). The minimum cardinality of a (Steiner) geodetic set is the (Steiner) geodetic number \(g(G)\) (resp. \(sg(G)\)). \(G\) is 3-Steiner distance hereditary (3-SDH) if for every 3-vertex set \(S\subset V\) the size of a Steiner subtree for \(S\) is independent from the induced subgraph it is calculated in. \(G\) is HHD-free (house-hole-domino-free) if every cycle of length at least 5 contains at least two chords. A contour vertex of \(G\) maximizes the largest of the distances to all \(v\in V\) over all its neighbours. It is shown that the contour vertices of any 3-SDH or HHD-free graph form a geodetic set. For 3-SDH graphs it is proven that \(g(G)\leq sg(G)\), and an efficient algorithm is described to determine Steiner intervals, i.e. the union of all Steiner subtrees for a given \(S\) in \(G\).
reviewed by: Frank Plastria
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 5321291
zbMATH Keywords: 3-Steiner distance hereditary
zbMATH Keywords: contour vertices
zbMATH Keywords: geodetic set
zbMATH Keywords: Steiner geodetic set
zbMATH Keywords: geodetic number
zbMATH Keywords: Steiner geodetic number
MaRDI profile type: Publication
full work available at URL: j.disc.2007.08.052
OpenAlex ID: W1964148783
cites work: Computational Complexity of Geodetic Set
cites work: Distance-hereditary graphs
cites work: Q4712025
cites work: The Shapley value on convex geometries
cites work: Graph Classes: A Survey
cites work: Q4350166
cites work: Geodetic sets in graphs
cites work: Rebuilding convex sets in graphs
cites work: Geodeticity of the contour of chordal graphs
cites work: Steiner Distance-Hereditary Graphs
cites work: A characterization of 3-Steiner distance hereditary graphs
cites work: Convexity in Graphs and Hypergraphs
cites work: Q4532748
cites work: Completely separable graphs
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: A characterization of ptolemaic graphs
cites work: Q3890733
cites work: Q4955672
cites work: Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs
cites work: Q3141898
DOI: 10.1016/J.DISC.2007.08.052
description: scientific article; zbMATH DE number 5321291