- Tytuł:
- Universality for and in Induced-Hereditary Graph Properties
- Autorzy:
-
Broere, Izak
Heidema, Johannes - Powiązania:
- https://bibliotekanauki.pl/articles/30146860.pdf
- Data publikacji:
- 2013-03-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
countable graph
universal graph
induced-hereditary property - Opis:
- The well-known Rado graph $R$ is universal in the set of all countable graphs \( \mathcal{I} \), since every countable graph is an induced subgraph of $R$. We study universality in \( \mathcal{I} \) and, using $R$, show the existence of $2^{\aleph_0}$ pairwise non-isomorphic graphs which are universal in \( \mathcal{I} \) and denumerably many other universal graphs in \( \mathcal{I} \) with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary properties contain no universal graphs. This is made precise by showing that there are $ 2^{2^{\aleph_0 } }$ properties in the lattice $ \mathbb{K}_\le $ of induced-hereditary properties of which only at most $ 2^{\aleph_0} $ contain universal graphs. In a final section we discuss the outlook on future work; in particular the question of characterizing those induced-hereditary properties for which there is a universal graph in the property.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 33-47
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł