Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Simplex_graph> ?p ?o }
Showing triples 1 to 53 of
53
with 100 triples per page.
- Simplex_graph abstract "In graph theory, a branch of mathematics, the simplex graph κ(G) of an undirected graph G is itself a graph, with one node for each clique (a set of mutually adjacent vertices) in G. Two nodes of κ(G) are linked by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex.The empty set is included as one of the cliques of G that are used to form the clique graph, as is every set of one vertex and every set of two adjacent vertices. Therefore, the simplex graph contains within it a subdivision of G itself. The simplex graph of a complete graph is a hypercube graph, and the simplex graph of a cycle graph of length four or more is a gear graph. The simplex graph of the complement graph of a path graph is a Fibonacci cube.The complete subgraphs of G can be given the structure of a median algebra: the median of three cliques A, B, and C is formed by the vertices that belong to a majority of the three cliques. Any two vertices belonging to this median set must both belong to at least one of A, B, or C, and therefore must be linked by an edge, so the median of three cliques is itself a clique. The simplex graph is the median graph corresponding to this median algebra structure. When G is the complement graph of a bipartite graph, the cliques of G can be given a stronger structure as a distributive lattice, and in this case the simplex graph is the graph of the lattice. As is true for median graphs more generally, every simplex graph is itself bipartite.The simplex graph has one vertex for every simplex in the clique complex X(G) of G, and two vertices are linked by an edge when one of the two corresponding simplexes is a facet of the other. Thus, the objects (vertices in the simplex graph, simplexes in X(G)) and relations between objects (edges in the simplex graph, inclusion relations between simplexes in X(G)) are in one-to-one correspondence between X(G) and κ(G).Simplex graphs were introduced by Bandelt & van de Vel (1989), who observed that a simplex graph has no cubes if and only if the underlying graph is triangle-free, and showed that the chromatic number of the underlying graph equals the minimum number n such that the simplex graph can be isometrically embedded into a Cartesian product of n trees. As a consequence of the existence of triangle-free graphs with high chromatic number, they showed that there exist two-dimensional topological median algebras that cannot be embedded into products of finitely many real trees. Imrich, Klavžar & Mulder (1999) also use simplex graphs as part of their proof that testing whether a graph is triangle-free or whether it is a median graph may be performed equally quickly.".
- Simplex_graph thumbnail Simplex_graph.svg?width=300.
- Simplex_graph wikiPageExternalLink 439.
- Simplex_graph wikiPageID "20752774".
- Simplex_graph wikiPageLength "5555".
- Simplex_graph wikiPageOutDegree "29".
- Simplex_graph wikiPageRevisionID "657375934".
- Simplex_graph wikiPageWikiLink Bipartite_graph.
- Simplex_graph wikiPageWikiLink Cartesian_product_of_graphs.
- Simplex_graph wikiPageWikiLink Category:Graph_families.
- Simplex_graph wikiPageWikiLink Category:Graph_operations.
- Simplex_graph wikiPageWikiLink Chromatic_number.
- Simplex_graph wikiPageWikiLink Clique_(graph_theory).
- Simplex_graph wikiPageWikiLink Clique_complex.
- Simplex_graph wikiPageWikiLink Complement_graph.
- Simplex_graph wikiPageWikiLink Complete_graph.
- Simplex_graph wikiPageWikiLink Cycle_graph.
- Simplex_graph wikiPageWikiLink Distributive_lattice.
- Simplex_graph wikiPageWikiLink Fibonacci_cube.
- Simplex_graph wikiPageWikiLink Gear_graph.
- Simplex_graph wikiPageWikiLink Graph_coloring.
- Simplex_graph wikiPageWikiLink Graph_theory.
- Simplex_graph wikiPageWikiLink Homeomorphism_(graph_theory).
- Simplex_graph wikiPageWikiLink Hypercube_graph.
- Simplex_graph wikiPageWikiLink List_of_graphs.
- Simplex_graph wikiPageWikiLink Majority_function.
- Simplex_graph wikiPageWikiLink Mathematics.
- Simplex_graph wikiPageWikiLink Median_algebra.
- Simplex_graph wikiPageWikiLink Median_graph.
- Simplex_graph wikiPageWikiLink Mycielskian.
- Simplex_graph wikiPageWikiLink Path_graph.
- Simplex_graph wikiPageWikiLink Real_tree.
- Simplex_graph wikiPageWikiLink SIAM_Journal_on_Discrete_Mathematics.
- Simplex_graph wikiPageWikiLink Subdivision_(graph_theory).
- Simplex_graph wikiPageWikiLink Triangle-free_graph.
- Simplex_graph wikiPageWikiLink File:Simplex_graph.svg.
- Simplex_graph wikiPageWikiLinkText "Simplex graph".
- Simplex_graph wikiPageWikiLinkText "simplex graph".
- Simplex_graph hasPhotoCollection Simplex_graph.
- Simplex_graph wikiPageUsesTemplate Template:Citation.
- Simplex_graph wikiPageUsesTemplate Template:Harvtxt.
- Simplex_graph wikiPageUsesTemplate Template:Reflist.
- Simplex_graph subject Category:Graph_families.
- Simplex_graph subject Category:Graph_operations.
- Simplex_graph type Graph.
- Simplex_graph comment "In graph theory, a branch of mathematics, the simplex graph κ(G) of an undirected graph G is itself a graph, with one node for each clique (a set of mutually adjacent vertices) in G. Two nodes of κ(G) are linked by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex.The empty set is included as one of the cliques of G that are used to form the clique graph, as is every set of one vertex and every set of two adjacent vertices.".
- Simplex_graph label "Simplex graph".
- Simplex_graph sameAs m.055bvb6.
- Simplex_graph sameAs Q7520883.
- Simplex_graph sameAs Q7520883.
- Simplex_graph wasDerivedFrom Simplex_graph?oldid=657375934.
- Simplex_graph depiction Simplex_graph.svg.
- Simplex_graph isPrimaryTopicOf Simplex_graph.