Simplex graph
Encyclopedia
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 , 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 algebra
s that cannot be embedded into products of finitely many real tree
s. 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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a branch of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the simplex graph κ(G) of an undirected graph G is itself a graph, with one node for each clique
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
(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
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
is a hypercube graph, and the simplex graph of a cycle graph
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
of length four or more is a gear graph. The simplex graph of the complement graph
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of a path graph
Path graph
In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
is a Fibonacci cube
Fibonacci cube
The Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in Number Theory. Mathematically they are similar to the hypercube graphs, but with a Fibonacci number of vertices, studied in graph-theoretic mathematics...
.
The complete subgraphs of G can be given the structure of a median algebra
Median algebra
In mathematics, a median algebra is a set with a ternary operation < x,y,z > satisfying a set of axioms which generalise the notion of median or majority function, as a Boolean function.The axioms are# < x,y,y > = y...
: the median of three cliques A, B, and C is formed by the vertices that belong to a majority
Majority function
In Boolean logic, the majority function is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise....
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
Median graph
In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...
corresponding to this median algebra structure. When G is the complement graph
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of a bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
, the cliques of G can be given a stronger structure as a distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
, 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
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
.
The simplex graph has one vertex for every simplex in the clique complex
Clique complex
Clique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.-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 , who observed that a simplex graph has no cubes if and only if the underlying graph is triangle-free
Triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
, 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
Cartesian product of graphs
In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that* the vertex set of G \square H is the Cartesian product V × V; and...
of n trees. As a consequence of the existence of triangle-free graphs with high chromatic number
Mycielskian
In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph G is a graph μ formed from G by a construction of , who used it to show that there exist triangle-free graphs with arbitrarily large chromatic number.-Construction:Let the n vertices of the given...
, they showed that there exist two-dimensional topological median algebra
Median algebra
In mathematics, a median algebra is a set with a ternary operation < x,y,z > satisfying a set of axioms which generalise the notion of median or majority function, as a Boolean function.The axioms are# < x,y,y > = y...
s that cannot be embedded into products of finitely many real tree
Real tree
A real tree, or an \mathbb R-tree, is a metric space such thatfor any x, y in M there is a unique arc from x to y and this arc is a geodesic segment. Here by an arc from x to y we mean the image in M of a topological embedding f from an interval [a,b] to M such that f=x and f=y...
s. 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.