Fiber-complemented graphs - I: structure and invariant subgraphs

A subset A of a metric space (X, d) is a prefiber (or a gated set) of X if, for every x epsilon X, there exists y epsilon A such that d(x,z) = d(x, y) + d(y,z) for every z epsilon A. In a graph endowed with the structure of metric space associated with the geodesic distance, the prefibers induce a convexity. In this paper, we introduce the class of fiber-complemented graphs fbr which the inverse image of every prefiber, by any projection map, onto a prefiber is a prefiber. I;rom this property we deduce: (1) a procedure of construction by amalgamation or by expansion where the minimal prefibers with respect to inclusion (called elementary prefibers) work like building stones and depend on each class of graphs; (2) a theorem of canonical isometric embedding into a Cartesian product of graphs whose factors, called elementary graphs, are induced by elementary prefibers. Then, we study the topology of these graphs, with respect to the convexity induced by the prefibers, in order to determine its subbase and to characterize compact fiber-complemented graphs. From this, we deduce that every fiber-complemented graph without isometric ray contains a Cartesian product of elementary graphs which is invariant under every automorphism. As a consequence, this theory gives a global approach to obtain several previous results related to median graphs, quasi-median graphs, pseudo-median graphs, weakly median graphs, bridged graphs, and extend them to the infinite case. (C) 2001 Elsevier Science B.V. All rights reserved.