Name
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 2(aleph 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(aleph 0)) properties in the lattice K <= 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.7151/dmgt.1671 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
countable graph,universal graph,induced-hereditary property | Discrete mathematics,Indifference graph,Combinatorics,Forbidden graph characterization,Chordal graph,Rado graph,Cograph,Graph product,Universal graph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
33 | 1 | 1234-3099 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Izak Broere | 1 | 143 | 31.30 |
| Johannes Heidema | 2 | 30 | 6.96 |