Universal elements and the complexity of certain classes of infinite graphs
A class of graphs is said to have a universal element \(G\) if every other element of the class is isomorphic to an induced subgraph of \(G\). The authors give a survey of some recent developments in the topic in the following areas: (1) graphs universal for isometric embeddings, (2) universal random graphs, (3) universal graphs with forbidden subgraphs, and (4) same with forbidden topological subgraphs. A new measure of complexity of a class with universal element is introduced and investigated. Finally, some analogous questions for hypergraphs are considered.
scientific article; zbMATH DE number 63139
scientific article