Page 1

Displaying 1 – 2 of 2

Showing per page

Universality for and in Induced-Hereditary Graph Properties

Izak Broere, Johannes Heidema (2013)

Discussiones Mathematicae Graph Theory

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...

Universality in Graph Properties with Degree Restrictions

Izak Broere, Johannes Heidema, Peter Mihók (2013)

Discussiones Mathematicae Graph Theory

Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m’th position of its binary expansion. It is well known that R is a universal graph in the set [...] of all countable graphs (since every graph in [...] is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of [...] is provided. We then construct...

Currently displaying 1 – 2 of 2

Page 1