Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Universal_graph> ?p ?o }
Showing triples 1 to 41 of
41
with 100 triples per page.
- Universal_graph abstract "In mathematics, a universal graph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by R. Rado and is now called the Rado graph or random graph. More recent workhas focused on universal graphs for a graph family F: that is, an infinite graph belonging to F that contains all finite graphs in F.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 graphso 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-node trees with only n vertices and O(n log n) edges, and that this is optimal. 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. 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.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.In older mathematical terminology, the phrase "universal graph" was sometimes used to denote a complete graph.".
- Universal_graph wikiPageID "1452141".
- Universal_graph wikiPageLength "6644".
- Universal_graph wikiPageOutDegree "16".
- Universal_graph wikiPageRevisionID "632039652".
- Universal_graph wikiPageWikiLink Category:Graph_families.
- Universal_graph wikiPageWikiLink Category:Infinite_graphs.
- Universal_graph wikiPageWikiLink Complete_graph.
- Universal_graph wikiPageWikiLink Countable.
- Universal_graph wikiPageWikiLink Countable_set.
- Universal_graph wikiPageWikiLink Glossary_of_graph_theory.
- Universal_graph wikiPageWikiLink Graph_(mathematics).
- Universal_graph wikiPageWikiLink Hypercube_graph.
- Universal_graph wikiPageWikiLink Implicit_graph.
- Universal_graph wikiPageWikiLink Induced_subgraph.
- Universal_graph wikiPageWikiLink Mathematics.
- Universal_graph wikiPageWikiLink Planar_graph.
- Universal_graph wikiPageWikiLink Planar_separator_theorem.
- Universal_graph wikiPageWikiLink Polytree.
- Universal_graph wikiPageWikiLink Rado_graph.
- Universal_graph wikiPageWikiLink Sumners_conjecture.
- Universal_graph wikiPageWikiLink Tournament_(graph_theory).
- Universal_graph wikiPageWikiLinkText "universal graph".
- Universal_graph wikiPageWikiLinkText "universal planar graph".
- Universal_graph hasPhotoCollection Universal_graph.
- Universal_graph wikiPageUsesTemplate Template:Reflist.
- Universal_graph subject Category:Graph_families.
- Universal_graph subject Category:Infinite_graphs.
- Universal_graph hypernym Graph.
- Universal_graph type Article.
- Universal_graph type Software.
- Universal_graph type Article.
- Universal_graph type Graph.
- Universal_graph comment "In mathematics, a universal graph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by R. Rado and is now called the Rado graph or random graph.".
- Universal_graph label "Universal graph".
- Universal_graph sameAs Grafo_universal.
- Universal_graph sameAs m.052pjs.
- Universal_graph sameAs Q7894131.
- Universal_graph sameAs Q7894131.
- Universal_graph wasDerivedFrom Universal_graph?oldid=632039652.
- Universal_graph isPrimaryTopicOf Universal_graph.