dc.contributor.author |
Broere, Izak
|
|
dc.contributor.author |
Heidema, Johannes
|
|
dc.date.accessioned |
2014-05-29T07:46:05Z |
|
dc.date.available |
2014-05-29T07:46:05Z |
|
dc.date.issued |
2013 |
|
dc.description.abstract |
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 20 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(20 ) properties in the lattice K< of induced-hereditary properties of which
only at most 20 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. |
en_US |
dc.description.librarian |
am2014 |
en_US |
dc.description.uri |
http://www.discuss.wmie.uz.zgora.pl/gt/ |
en_US |
dc.identifier.citation |
Broere, I & Heidema, J 2013, 'Universality for and in induced-hereditary graph properties', Discussiones Mathematicae Graph Theory, vol. 33, no. 1, pp. 34-47. |
en_US |
dc.identifier.issn |
1234-3099 (print) |
|
dc.identifier.issn |
2083-5892 (online) |
|
dc.identifier.other |
10.7151/dmgt.1671 |
|
dc.identifier.uri |
http://hdl.handle.net/2263/39916 |
|
dc.language.iso |
en |
en_US |
dc.rights |
Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra |
en_US |
dc.subject |
Countable graph |
en_US |
dc.subject |
Universal graph |
en_US |
dc.subject |
Induced-hereditary property |
en_US |
dc.title |
Universality for and in induced-hereditary graph properties |
en_US |
dc.type |
Article |
en_US |