Universal graph

Source: Wikipedia, the free encyclopedia.

In

countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado[1][2] and is now called the Rado graph or random graph. More recent work[3]
[4] has focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F. For instance, the Henson graphs are universal in this sense for the i-clique-free graphs.

A universal graph for a family F of graphs can also refer to a member of a sequence of finite graphs that contains all graphs in F; for instance, every finite tree is a subgraph of a sufficiently large hypercube graph[5] so a hypercube can be said to be a universal graph for trees. However it is not the smallest such graph: it is known that there is a universal graph for n-vertex trees, with only n vertices and O(n log n) edges, and that this is optimal.[6] A construction based on the planar separator theorem can be used to show that n-vertex planar graphs have universal graphs with O(n3/2) edges, and that bounded-degree planar graphs have universal graphs with O(n log n) edges.[7][8][9] It is also possible to construct universal graphs for planar graphs that have n1+o(1) vertices.[10] Sumner's conjecture states that tournaments are universal for polytrees, in the sense that every tournament with 2n − 2 vertices contains every polytree with n vertices as a subgraph.[11]

A family F of graphs has a universal graph of polynomial size, containing every n-vertex graph as an induced subgraph, if and only if it has an adjacency labelling scheme in which vertices may be labeled by O(log n)-bit bitstrings such that an algorithm can determine whether two vertices are adjacent by examining their labels. For, if a universal graph of this type exists, the vertices of any graph in F may be labeled by the identities of the corresponding vertices in the universal graph, and conversely if a labeling scheme exists then a universal graph may be constructed having a vertex for every possible label.[12]

In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph.

The notion of universal graph has been adapted and used for solving mean payoff games.[13]

References

  1. MR 0172268
    .
  2. MR 0214507
    .
  3. MR 1428038
    .
  4. S2CID 17529604
    .
  5. ^ Wu, A. Y. (1985). "Embedding of tree networks into hypercubes". Journal of Parallel and Distributed Computing. 2 (3): 238–249.
    doi:10.1016/0743-7315(85)90026-7
    .
  6. MR 0692525
    ..
  7. MR 0806964
    .
  8. MR 0990447
    .
  9. MR 1083375
    .
  10. doi:10.1145/3477542
  11. ^ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
  12. MR 1186827
    .
  13. S2CID 51865783
    .

External links
Retrieved from "https://en.wikipedia.org/w/index.php?title=Universal_graph&oldid=1112303554"