Universality for and in Induced-Hereditary Graph Properties
The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal gra...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2013-03-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1671 |
| _version_ | 1797757731361259520 |
|---|---|
| author | Broere Izak Heidema Johannes |
| author_facet | Broere Izak Heidema Johannes |
| author_sort | Broere Izak |
| collection | DOAJ |
| description | The well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in 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א0 ) properties in the lattice K ≤ of induced-hereditary properties of which only at most 2א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. |
| first_indexed | 2024-03-12T18:19:47Z |
| format | Article |
| id | doaj.art-0ae60690bb56457ba89ccddf7d93e424 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:47Z |
| publishDate | 2013-03-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-0ae60690bb56457ba89ccddf7d93e4242023-08-02T08:58:21ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-03-01331334710.7151/dmgt.1671Universality for and in Induced-Hereditary Graph PropertiesBroere Izak0Heidema Johannes1Department of Mathematics and Applied Mathematics University of PretoriaDepartment of Mathematical Sciences University of South AfricaThe well-known Rado graph R is universal in the set of all countable graphs I, since every countable graph is an induced subgraph of R. We study universality in I and, using R, show the existence of 2 א0 pairwise non-isomorphic graphs which are universal in I and denumerably many other universal graphs in 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א0 ) properties in the lattice K ≤ of induced-hereditary properties of which only at most 2א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.https://doi.org/10.7151/dmgt.1671countable graphuniversal graphinduced-hereditary property |
| spellingShingle | Broere Izak Heidema Johannes Universality for and in Induced-Hereditary Graph Properties Discussiones Mathematicae Graph Theory countable graph universal graph induced-hereditary property |
| title | Universality for and in Induced-Hereditary Graph Properties |
| title_full | Universality for and in Induced-Hereditary Graph Properties |
| title_fullStr | Universality for and in Induced-Hereditary Graph Properties |
| title_full_unstemmed | Universality for and in Induced-Hereditary Graph Properties |
| title_short | Universality for and in Induced-Hereditary Graph Properties |
| title_sort | universality for and in induced hereditary graph properties |
| topic | countable graph universal graph induced-hereditary property |
| url | https://doi.org/10.7151/dmgt.1671 |
| work_keys_str_mv | AT broereizak universalityforandininducedhereditarygraphproperties AT heidemajohannes universalityforandininducedhereditarygraphproperties |