Fiber-complemented graphs. I: Structure and invariant subgraphs
type: Item
instance of: scholarly article
title: Fiber-complemented graphs. I: Structure and invariant subgraphs
zbMATH Open document ID: 0961.05019
DOI: 10.1016/S0012-365X(00)00183-7
author: Marc Chastand
published in: Discrete Mathematics
publication date: 2001-05-21T00:00:00Z
review text: A vertex subset of a (possibly infinite) graph is a prefiber (gated set) when from each exterior vertex all vertices of this subset are reachable by a geodesic (shortest path) which passes through one particular subset-vertex, called its projection on the prefiber. The graph is fiber-complemented (FC) if inverse projection-images of prefibers are always prefibers. All FC graphs may be constructed by iterated expansions of \(K_1\) by inclusion-minimal elementary graphs, and also by amalgamations of Cartesian products of such elementary graphs (a characterisation in general remains open). Median-, quasi-median-, pseudo-median-, weakly median- and bridged graphs are FC graphs, generated by particular (and known) families of elementary graphs. Any FC graph is isometrically embeddable in a Cartesian product of elementary graphs. Its prefibers generate a convexity structure and hence a topology on the vertex set, for which a full characterisation of compactness and compact Hausdorffness is obtained. This structural analysis allows to derive in a unified way (including infinite graphs) several other structural properties previously obtained for the different special subclasses of finite FC graphs.
reviewed by: Frank Plastria
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1565935
zbMATH Keywords: discrete metric space
zbMATH Keywords: prefiber
zbMATH Keywords: gated set
zbMATH Keywords: fiber-complemented graph
zbMATH Keywords: median graph
zbMATH Keywords: quasi-median graph
zbMATH Keywords: pseudo-median graph
zbMATH Keywords: bridged graph convexity
zbMATH Keywords: Cartesian product
zbMATH Keywords: isometric embedding
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00183-7
OpenAlex ID: W2051456269
description: scientific article; zbMATH DE number 1565935