Clebsch graph

Last updated
Clebsch graph
Clebsch Lombardi.svg
Named after Alfred Clebsch
Vertices 16
Edges 40
Radius 2
Diameter 2
Girth 4
Automorphisms 1920
Chromatic number 4 [1]
Chromatic index 5
Book thickness 4
Queue number 3
Properties Strongly regular
Hamiltonian
Cayley graph
Vertex-transitive
Edge-transitive
Distance-transitive.
Table of graphs and parameters

In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) [2] because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the dimension-5 folded cube graph; it is also known as the GreenwoodGleason graph after the work of Robert E.Greenwoodand Andrew M. Gleason  ( 1955 ), who used it to evaluate the Ramsey number R(3,3,3) = 17. [3] [4] [5]

Contents

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 GF(16), and connect two vertices by an edge whenever the difference between the corresponding two field elements is a perfect cube. [6]

The dimension-5 halved cube graph (the 10-regular Clebsch graph) is the complement 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 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-squares of the hypercube are isomorphic 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 of degree 5 with parameters . [7] [8] Its complement, the 10-regular Clebsch graph, is therefore also a strongly regular graph, [1] [4] with parameters .

The 5-regular Clebsch graph is 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 copy of the Petersen graph.

It has book thickness 4 and queue number 3. [9]

K16 3-coloured as three Clebsch graphs. K 16 partitioned into three Clebsch graphs.svg
K16 3-coloured as three Clebsch graphs.

The edges of the complete graph K16 may be partitioned into three disjoint copies of the 5-regular Clebsch graph. Because the Clebsch graph is a triangle-free graph, this shows that there is a triangle-free three-coloring of the edges of K16; that is, that the Ramsey number R(3,3,3) describing the minimum number of vertices in a complete graph without a triangle-free three-coloring is at least 17. Greenwood & Gleason (1955) used this construction as part of their proof that R(3,3,3) = 17. [5] [10]

The 5-regular Clebsch graph may be colored 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 the Grötzsch graph, 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 of length six or more is an induced subgraph of the Clebsch graph and an induced supergraph of the Grötzsch graph. [11]

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 spaces by hypercubes 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 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 consists entirely of integers. [4] 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 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 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.

Related Research Articles

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

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 named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is an automorphism of G that maps e1 to e2.

<span class="mw-page-title-main">Desargues graph</span> Distance-transitive cubic graph with 20 nodes and 30 edges

In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

<span class="mw-page-title-main">Hoffman–Singleton graph</span> 7-regular undirected graph with 50 nodes and 175 edges

In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest-order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.

<span class="mw-page-title-main">Butterfly graph</span> Planar graph with 5 nodes and 6 edges

In the mathematical field of graph theory, the butterfly graph is a planar, undirected graph with 5 vertices and 6 edges. It can be constructed by joining 2 copies of the cycle graph C3 with a common vertex and is therefore isomorphic to the friendship graph F2.

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<span class="mw-page-title-main">Rook's graph</span> Graph of chess rook moves

In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.

<span class="mw-page-title-main">Grötzsch graph</span> Triangle-free graph requiring four colors

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 in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.

<span class="mw-page-title-main">Möbius–Kantor graph</span>

In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen graph G(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.

<span class="mw-page-title-main">Wagner graph</span> Cubic graph with 8 vertices and 12 edges

In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.

<span class="mw-page-title-main">Diamond graph</span> Planar graph with 4 nodes and 5 edges

In the mathematical field of graph theory, the diamond graph is a planar, undirected graph with 4 vertices and 5 edges. It consists of a complete graph minus one edge.

<span class="mw-page-title-main">Ljubljana graph</span> Undirected bipartite graph with 112 vertices and 168 edges

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges, rediscovered in 2002 and named after Ljubljana.

<span class="mw-page-title-main">Hoffman graph</span>

In the mathematical field of graph theory, the Hoffman graph is a 4-regular graph with 16 vertices and 32 edges discovered by Alan Hoffman. Published in 1963, it is cospectral to the hypercube graph Q4.

<span class="mw-page-title-main">Gosset graph</span>

The Gosset graph, named after Thorold Gosset, is a specific regular graph (1-skeleton of the 7-dimensional 321 polytope) with 56 vertices and valency 27.

<span class="mw-page-title-main">Folded cube graph</span> Undirected graph derived from a hypercube graph

In graph theory, a folded cube graph is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects opposite pairs of hypercube vertices.

<span class="mw-page-title-main">Schläfli graph</span>

In the mathematical field of graph theory, the Schläfli graph, named after Ludwig Schläfli, is a 16-regular undirected graph with 27 vertices and 216 edges. It is a strongly regular graph with parameters srg(27, 16, 10, 8).

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

<span class="mw-page-title-main">Italo Jose Dejter</span>

Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

<span class="mw-page-title-main">Halved cube graph</span> Graph of the vertices and edges of a demihypercube

In graph theory, the halved cube graph or half cube graph of dimension n 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 of the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph.

References

  1. 1 2 Weisstein, Eric W. "Clebsch Graph". From MathWorld—A Wolfram Web Resource. Retrieved 2009-08-13.
  2. J. J. Seidel, Strongly regular graphs with (−1,1,0) adjacency matrix having eigenvalue 3, Lin. Alg. Appl. 1 (1968) 281-298.
  3. Clebsch, A. (1868), "Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen", Journal für die reine und angewandte Mathematik, 69: 142–184.
  4. 1 2 3 "The Clebsch Graph on Bill Cherowitzo's home page" (PDF). Archived from the original (PDF) on 2013-10-29. Retrieved 2011-05-21.
  5. 1 2 Greenwood, R. E.; Gleason, A. M. (1955), "Combinatorial relations and chromatic graphs", Canadian Journal of Mathematics, 7: 1–7, doi: 10.4153/CJM-1955-001-4 , MR   0067467 .
  6. De Clerck, Frank (1997). "Constructions and Characterizations of (Semi)partial Geometries". Summer School on Finite Geometries. p. 6.
  7. Godsil, C.D. (1995). "Problems in algebraic combinatorics" (PDF). Electronic Journal of Combinatorics . 2: 3. doi:10.37236/1224 . Retrieved 2009-08-13.
  8. Peter J. Cameron Strongly regular graphs on DesignTheory.org, 2001
  9. Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  10. Sun, Hugo S.; Cohen, M. E. (1984), "An easy proof of the Greenwood–Gleason evaluation of the Ramsey number R(3,3,3)" (PDF), The Fibonacci Quarterly, 22 (3): 235–238, MR   0765316 .
  11. Randerath, Bert; Schiermeyer, Ingo; Tewes, Meike (2002), "Three-colourability and forbidden subgraphs. II. Polynomial algorithms", Discrete Mathematics , 251 (1–3): 137–153, doi: 10.1016/S0012-365X(01)00335-1 , MR   1904597 .