Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs (Q941349): Difference between revisions

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\).