In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the Clebsch graph is either of two
complementary
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class ...
graphs on 16 vertices, a 5-
regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree ...
with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5
halved cube graph
In graph theory, the halved cube graph or half cube graph of dimension is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square o ...
; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician
Alfred Clebsch
Rudolf Friedrich Alfred Clebsch (19 January 1833 – 7 November 1872) was a German mathematician who made important contributions to algebraic geometry and invariant theory. He attended the University of Königsberg and was habilitated at Berlin. ...
. The 40-edge variant is the dimension-5
folded cube graph; it is also known as the Greenwood–Gleason graph after the work of , who used it to evaluate the
Ramsey number
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (sa ...
''R''(3,3,3) = 17.
[The Clebsch Graph on Bill Cherowitzo's home page](_blank)
/ref>[.]
Construction
The dimension-5 folded cube graph (the 5-regular Clebsch graph) may be constructed by adding edges between opposite pairs of vertices in a 4-dimensional hypercube graph. (In an ''n''-dimensional hypercube, a pair of vertices are ''opposite'' if the shortest path between them has ''n'' edges.) Alternatively, it can be formed from a 5-dimensional hypercube graph by identifying together (or contracting) every opposite pair of vertices.
Another construction, leading to the same graph, is to create a vertex for each element of the finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
GF(16), and connect two vertices by an edge whenever the difference between the corresponding two field elements is a perfect cube
In arithmetic and algebra, the cube of a number is its third power, that is, the result of multiplying three instances of together.
The cube of a number or any other mathematical expression is denoted by a superscript 3, for example or .
T ...
.
The dimension-5 halved cube graph
In graph theory, the halved cube graph or half cube graph of dimension is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square o ...
(the 10-regular Clebsch graph) is the complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class ...
of the 5-regular graph. It may also be constructed from the vertices of a 5-dimensional hypercube, by connecting pairs of vertices whose Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chang ...
is exactly two. This construction is an instance of the construction of Frankl–Rödl graphs. It produces two subsets of 16 vertices that are disconnected from each other; both of these half-square
In graph theory, the bipartite half or half-square of a bipartite graph is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, ) and in which there is an edge for each pair of vertices in that are ...
s of the hypercube are isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
to the 10-regular Clebsch graph. Two copies of the 5-regular Clebsch graph can be produced in the same way from a 5-dimensional hypercube, by connecting pairs of vertices whose Hamming distance is exactly four.
Properties
The 5-regular Clebsch graph is a strongly regular graph
In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that:
* Every two adjacent vertices have comm ...
of degree 5 with parameters .
Its complement, the 10-regular Clebsch graph, is therefore also a strongly regular graph, with parameters .
The 5-regular Clebsch graph is hamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
, non planar and non eulerian. It is also both 5- vertex-connected and 5- edge-connected. The subgraph that is induced by the ten non-neighbors of any vertex in this graph forms an isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
copy of the Petersen graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is ...
.
It has book thickness
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie o ...
4 and queue number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
Defin ...
3.
The edges of the 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. A complete digraph is a directed graph in which every pair of distinct vertices is ...
''K''16 may be partitioned into three disjoint copies of the 5-regular Clebsch graph. Because the Clebsch graph is a 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 ...
, this shows that there is a triangle-free three-coloring of the edges of ''K''16; that is, that the Ramsey number
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (sa ...
''R''(3,3,3) describing the minimum number of vertices in a complete graph without a triangle-free three-coloring is at least 17. used this construction as part of their proof that ''R''(3,3,3) = 17.
The 5-regular Clebsch graph may be colored
''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow Era to refer to an African American. In many places, it may be considered a slur, though it has taken on a special meaning in South ...
with four colors, but not three: its largest independent set has five vertices, not enough to partition the graph into three independent color classes. It contains as an induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Definit ...
the Grötzsch graph
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example i ...
, the smallest triangle-free four-chromatic graph, and every four-chromatic induced subgraph of the Clebsch graph is a supergraph of the Grötzsch graph. More strongly, every triangle-free four-chromatic graph with no induced path
In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...
of length six or more is an induced subgraph of the Clebsch graph and an induced supergraph of the Grötzsch graph.[.]
The 5-regular Clebsch graph is the Keller graph of dimension two, part of a family of graphs used to find tilings of high-dimensional Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean s ...
s by hypercube
In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perp ...
s no two of which meet face-to-face.
The 5-regular Clebsch graph can be embedded as a regular map in the orientable manifold of genus 5, forming pentagonal faces; and in the non-orientable surface of genus 6, forming tetragonal faces.
Algebraic properties
The characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The char ...
of the 5-regular Clebsch graph is . Because this polynomial can be completely factored into linear terms with integer coefficients, the Clebsch graph is an integral graph: its spectrum
A spectrum (plural ''spectra'' or ''spectrums'') is a condition that is not limited to a specific set of values but can vary, without gaps, across a continuum. The word was first used scientifically in optics to describe the rainbow of colors ...
consists entirely of integers. The Clebsch graph is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
The 5-regular Clebsch graph is a Cayley graph
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayl ...
with an automorphism group of order 1920, isomorphic to the Coxeter group . As a Cayley graph, its automorphism group acts transitively on its vertices, making it vertex transitive
In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face i ...
. In fact, it is arc transitive, hence edge transitive and distance transitive. It is also connected-homogeneous, meaning that every isomorphism between two connected induced subgraphs can be extended to an automorphism of the whole graph.
Gallery
File:Clebsch graph hamiltonian.svg, The Clebsch graph is Hamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
.
File:Complete coloring clebsch graph.svg, The achromatic number of the Clebsch graph is 8.
File:Clebsch graph 4COL.svg, The chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
of the Clebsch graph is 4.
File:Clebsch_graph_5color_edge.svg, The chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
of the Clebsch graph is 5.
File:Clebsch hypercube.svg, Construction of the Clebsch graph from a hypercube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has vertices, ...
.
References
{{reflist
Individual graphs
Regular graphs
Strongly regular graphs