On the Steiner, geodetic and hull numbers of graphs
type: Item
instance of: scholarly article
title: On the Steiner, geodetic and hull numbers of graphs
zbMATH Open document ID: 1062.05052
author: C. Hernando
author: Tao Jiang
author: I. M. Pelayo
author: Carlos Seara
author: Mercè Mora
published in: Discrete Mathematics
publication date: 2005-06-01T00:00:00Z
full work available at URL: http://hdl.handle.net/2117/868
review text: A Steiner set of a graph \(G\) is a subset \(W\) of \(V(G)\) such that all vertices of \(G\) lie on some tree of minimum order that contains all vertices of \(W\). The minimum order of a Steiner set of \(G\) is called the Steiner number of \(G\). Let \(I[u,v]\) and \(J[u,v]\) denote the set of all vertices in \(G\) lying on some \(u\)-\(v\) geodesic and on some induced \(u\)-\(v\) path, respectively. Given a set \(S\subseteq V(G)\), \(I[S]\) and \(J[S]\) denote the geodetic closure and the monophonic closure of \(S\), i.e., the union of all \(I[u,v]\) and \(J[u,v]\), respectively, over all \(u,v\in S\). If \(I[S]\) and \(J[S]\), respectively equals \(V(G)\), then \(S\) is called a geodetic and a monophonic set, respectively. The geodetic number of \(G\) is equal to the minimum order of a geodetic set in \(G\). In this paper relationships between Steiner sets and geodetic sets and between Steiner sets and monophonic sets are studied. It is shown, e.g., that every Steiner set in a connected graph must also be monophonic, and that every Steiner set in a connected interval graph must be geodetic. The authors prove that there exists a connected graph having prescribed pairs of hull, geodetic or Steiner numbers satisfying some inequalities.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 2173237
zbMATH Keywords: chordal graph
zbMATH Keywords: convexity
zbMATH Keywords: geodesic
zbMATH Keywords: geodetic set
zbMATH Keywords: geodetic number
zbMATH Keywords: hull number
zbMATH Keywords: monophonic set
zbMATH Keywords: Steiner set
zbMATH Keywords: Steiner number
MaRDI profile type: Publication
OpenAlex ID: W2102217150
cites work: On the hull number of a graph.
cites work: The Steiner number of a graph
cites work: Asteroidal Triple-Free Graphs
cites work: Convexity and HHD-Free Graphs
cites work: Characterizations of strongly chordal graphs
cites work: Convexity in Graphs and Hypergraphs
cites work: On local convexity in graphs
cites work: The geodetic number of a graph
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: A characterization of ptolemaic graphs
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Comment on ``The Steiner number of a graph'' by G. Chartrand and P. Zhang [Discrete Mathematics 242 (2002) 41--54]
cites work: Q3141898
DOI: 10.1016/J.DISC.2004.08.039
Recommended article: Q5173715
Recommended article: Analogies between the geodetic number and the Steiner number of some classes of graphs
Recommended article: Q4470357
Recommended article: The hull and geodetic numbers of orientations of graphs
Recommended article: Hull and geodetic numbers for some classes of oriented graphs
Recommended article: Geodetic sets and Steiner sets in graphs
Recommended article: On the geodetic hull number of \(P_{k}\)-free graphs
Recommended article: Q3537009
Recommended article: On the forcing geodetic and forcing steiner numbers of a graph
description: scientific article; zbMATH DE number 2173237