Back to Search
Start Over
Universality in graph properties allowing constrained growth
Universality in graph properties allowing constrained growth
- 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 .
- Subjects :
- Vertex (graph theory)
Epigraph
010102 general mathematics
Induced subgraph
Universality (philosophy)
0102 computer and information sciences
01 natural sciences
Combinatorics
Integer
010201 computation theory & mathematics
Discrete Mathematics and Combinatorics
0101 mathematics
Graph property
Finite character
Mathematics
Universal graph
Subjects
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