No label defined (Q3972522)

[For the entire collection see Zbl 0709.00011.] There are several classes of graphs that can be characterized by some elimination scheme: a special vertex can be deleted producing a smaller graph in the class. The most well-known example is probably that of chordal graphs (or triangulated graphs). Each chordal graph has a simplicial vertex, i.e. a vertex of which the neighbours induce a complete subgraph. Thus we get a `simplicial' elimination scheme. Other graphs having an elimination scheme are for instance trees, interval graphs, dismantlable graphs, and distance-hereditary graphs. Many results for these graphs have been proved using elimination and induction. By reversing the process we can produce all these graphs by specific one- vertex extensions from the one-vertex graph. In this paper we propose another type of construction to produce graphs from smaller ones: expansion. Loosely speaking the idea of expansion is the following. Let \(G\) be covered by a number of subgraphs, which two by two intersect in the same subgraph \(G_ 0\) of \(G\). Now we take the disjoint copies of the covering subgraphs and join the respective copies of \(G_ 0\) in these subgraphs by new edges. By imposing conditions on the covering subgraphs and on how to insert the new edges we get specific instances of expansion. Some types of expansion may not be sensible to study, but others seem to be quite promising in producing interesting problems and results. Thus we get some sort of a `masterplan' for studying expansion problems. To show how fruitful this approach can be, we discuss a number of results on median graphs and quasi-median graphs. These all have elegant and straightforward proofs using the expansion characterization of median graphs and quasi-median graphs. Although some of the ideas below make sense for infinite graphs as well, we assume that all graphs considered are finite.