Simplex graph

A graph G and the corresponding simplex graph κ(G).

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 (complete subgraph) 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 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. As is true for median graphs more generally, every simplex graph is bipartite.

The simplex graph is the intersection graph of the clique complex X(G) of G: it has one vertex for every simplex in X(G), and two vertices are linked by an edge when the corresponding simplices have a nonempty intersection. 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).

References

• Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J.E.; Pach, J.; Pollack, R. (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemp. Math., vol. 453, Providence, RI: AMS, pp. 49–86.