Clebsch graph

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) 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 Greenwood–Gleason graph after the work of , who used it to evaluate the Ramsey number R(3,3,3) = 17. 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. 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. The 5-regular Clebsch graph is a strongly regular graph of degree 5 with parameters .

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (3)

Related courses (1)

Related lectures (5)

FIN-406: Macrofinance

This course provides students with a working knowledge of macroeconomic models that explicitly incorporate financial markets. The goal is to develop a broad and analytical framework for analyzing the

Clebsch graph

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 independent graphs. By Turán's theorem, the n-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible.

Graph coloring

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 of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Understanding Surface Integrals

Explores surface integrals, emphasizing physical interpretation and mathematical calculations in vector fields and domains.

Labor Income Share

Analyzes a macroeconomic model focusing on labor income share and the effects of productivity shocks on GDP, consumption, investment, and stock prices.

Szemerédi Regularity Lemma

Explores the Szemerédi Regularity Lemma, e-regularity in bipartite graphs, supergraph structure, and induction techniques.