scientific article; zbMATH DE number 15874
[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.
- Cage-amalgamation graphs, a common generalization of chordal and median graphs
- Cube intersection concepts in median graphs
- Netlike partial cubes, V: completion and netlike classes
- Expanding graphs and invariant means
- The direct expansion of graphs
- The majority strategy on graphs
- The median procedure on median graphs
- Quasi-median graphs, their generalizations, and tree-like equalities
- Fast recognition algorithms for classes of partial cubes
- Geodetic spectra of graphs.
- An Euler-type formula for median graphs
- On subgraphs of Cartesian product graphs and S-primeness
- Intersection graphs of maximal hypercubes
- The geodetic number of an oriented graph
- The median function on median graphs and semilattices
- Medians in median graphs and their cube complexes in linear time
- Tree-like partial Hamming graphs
- The geodetic numbers of graphs and digraphs
- On median nature and enumerative properties of Fibonacci-like cubes
- Planar median graphs and cubesquare-graphs
- Θ-graphs of partial cubes and strong edge colorings
- Layouts of Expander Graphs
- On the Edge-Expansion of Graphs
- The shrinking-and-expanding method for the graph enumeration
- scientific article; zbMATH DE number 919838 (Why is no real title available?)
- Five axioms for location functions on median graphs
- What do trees and hypercubes have in common?
- Crossing graphs of fiber-complemented graphs
- Crossing graphs of fiber-complemented graphs
- Binary Coding of Resonance Graphs of Catacondensed Polyhexes
- A relation between the cube polynomials of partial cubes and the clique polynomials of their crossing graphs
- Weak geodesic topology and fixed finite subgraph theorems in infinite partial cubes. II: Fixed subgraph properties and infinite treelike partial cubes
- Boundary rigidity of CAT(0) cube complexes
- Medians in median graphs and their cube complexes in linear time
- Expansion in matrix-weighted graphs
- Maximal proper subgraphs of median graphs
- On the geodetic number of median graphs
- On the remoteness function in median graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972522)
