Universality in graph properties allowing constrained growth

Abstract

A graph property is a class of graphs which is closed under isomorphisms. Some properties are also closed under one or more specified constructions that extend any graph into a supergraph containing the original graph as an induced subgraph.We introduce and study in particular the concept that a property P “allows finite spiking” and show that there is a universal graph in every induced-hereditary property of finite character which allows finite spiking. We also introduce the concept that P “allows isolated vertex addition” and constructively show that there is a unique graph with the so-called P-extension property in every induced-hereditary property P of finite character which allows finite spiking and allows isolated vertex addition; such a graph is then universal in P too. Infinitely many examples which satisfy the conditions of both these results are obtained by taking the property of Kn-free graphs for an arbitrary integer n ≥ 2.