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.
