Simplex graph

Article summary

In graph theory, a branch of mathematics, the simplex graph of an undirected graph is itself a graph, with one node for each clique (a set of mutually adjacent vertices) in . Two nodes of 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 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 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 can be given the structure of a median algebra: the median of three cliques , , and 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 , , or , 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 is the complement graph of a bipartite graph, the cliques of can be given a stronger structure as a distributive lattice, and in this case the simplex graph is the graph of the lattice.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.