Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: induced-hereditary property

Sortuj według:

Ogranicz wyniki do:

Universality for and in Induced-Hereditary Graph Properties

100%

Broere I., Heidema J.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 1

33-47

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Broere I.

1 Heidema J.

1 2013

Wyniki wyszukiwania

Universality for and in Induced-Hereditary Graph Properties