Universality in graph properties allowing constrained growth

Loading...
Thumbnail Image

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.