Universality in graph properties allowing constrained growth
Loading...
Date
Authors
Broere, Izak
Heidema, Johannes
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
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.
Description
Keywords
Countable graph, Property of graphs, Universal graph, Finite character, Spiking
Sustainable Development Goals
Citation
I. Broere and J. Heidema, Universality in graph properties allowing constrained growth, AKCE International Journal of Graphs and Combinatorics (2019),
https://DOI.org/ 10.1016/j.akcej.2019.02.002. NYP.