Back to Search Start Over

Universality in graph properties allowing constrained growth

Universality in graph properties allowing constrained growth

Authors :
Johannes Heidema
Izak Broere
Source :
AKCE International Journal of Graphs and Combinatorics.
Publication Year :
2019
Publisher :
Informa UK Limited, 2019.

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 K n -free graphs for an arbitrary integer n ≥ 2 .

Details

ISSN :
09728600
Database :
OpenAIRE
Journal :
AKCE International Journal of Graphs and Combinatorics
Accession number :
edsair.doi...........0337e7c5bd05f5675f42395d2d9cff62
Full Text :
https://doi.org/10.1016/j.akcej.2019.02.002