# Category: Regular graphs

Robertson–Wegner graph
In the mathematical field of graph theory, the Robertson–Wegner graph is a 5-regular undirected graph with 30 vertices and 75 edges named after Neil Robertson and Gerd Wegner. It is one of the four (5
Semi-symmetric graph
In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. In other words, a graph is semi-symmetric if ea
Sudoku graph
In the mathematics of Sudoku, the Sudoku graph is an undirected graph whose vertices represent the cells of a (blank) Sudoku puzzle and whose edges represent pairs of cells that belong to the same row
Wagner graph
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.
Cage (graph theory)
In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an (r, g)-graph is defined to be a graph in which each vertex has exac
Klein graphs
In the mathematical field of graph theory, the Klein graphs are two different but related regular graphs, each with 84 edges. Each can be embedded in the orientable surface of genus 3, in which they f
McLaughlin graph
In the mathematical field of graph theory, the McLaughlin graph is a strongly regular graph with parameters (275,112,30,56), and is the only such graph. The group theorist Jack McLaughlin discovered t
Pappus graph
In the mathematical field of graph theory, the Pappus graph is a bipartite 3-regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named a
Gray graph
In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discover
Johnson graph
Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph are the -element subsets of an -element set; two vertices are adjacent when the
Snark (graph theory)
In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, sna
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 (at least 3, if the graph is simple) connected in a closed chain
Quartic graph
In the mathematical field of graph theory, a quartic graph is a graph where all vertices have degree 4. In other words, a quartic graph is a 4-regular graph.
Chang graphs
In the mathematical field of graph theory, the Chang graphs are a set of three 12-regular undirected graphs, each with 28 vertices and 168 edges. They are strongly regular, with the same parameters an
Supersingular isogeny graph
In mathematics, the supersingular isogeny graphs are a class of expander graphs that arise in computational number theory and have been applied in elliptic-curve cryptography. Their vertices represent
Half-transitive graph
In the mathematical field of graph theory, a half-transitive graph is a graph that is both vertex-transitive and edge-transitive, but not symmetric. In other words, a graph is half-transitive if its a
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 prob
Hoffman graph
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 Q
Meringer graph
In the mathematical field of graph theory, the Meringer graph is a 5-regular undirected graph with 30 vertices and 75 edges named after Markus Meringer. It is one of the four (5,5)-cage graphs, the ot
Strongly regular graph
In graph theory, a strongly regular graph (SRG) is defined as follows. Let G = (V, E) be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and
Hoffman–Singleton graph
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
Sylvester graph
The Sylvester graph is the unique distance-regular graphwith intersection array .It is a subgraph of the Hoffman–Singleton graph.
Wong graph
In the mathematical field of graph theory, the Wong graph is a 5-regular undirected graph with 30 vertices and 75 edges. It is one of the four (5,5)-cage graphs, the others being the Foster cage, the
Tutte graph
In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diamete
Andrásfai graph
In graph theory, an Andrásfai graph is a triangle-free, circulant graph named after Béla Andrásfai.
Antiprism graph
In the mathematical field of graph theory, an antiprism graph is a graph that has one of the antiprisms as its skeleton. An n-sided antiprism has 2n vertices and 4n edges. They are regular, polyhedral
Tutte 12-cage
In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte. The Tutte 12-cage is the unique (3-12)-cage (
Coxeter graph
In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott
Hypercube graph
In graph theory, the hypercube graph Qn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edge
Frucht graph
In the mathematical field of graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939. The Frucht graph
Cube-connected cycles
In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by for use as a network topology in parallel
Dipole graph
In graph theory, a dipole graph, dipole, bond graph, or linkage, is a multigraph consisting of two vertices connected with a number of parallel edges. A dipole graph containing n edges is called the o
Tutte–Coxeter graph
In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight-cage or Cremona–Richmond graph is a 3-regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph
Dyck graph
In the mathematical field of graph theory, the Dyck graph is a 3-regular graph with 32 vertices and 48 edges, named after Walther von Dyck. It is Hamiltonian with 120 distinct Hamiltonian cycles. It h
Null graph
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Dürer graph
In the mathematical field of graph theory, the Dürer graph is an undirected graph with 12 vertices and 18 edges. It is named after Albrecht Dürer, whose 1514 engraving Melencolia I includes a depictio
Triangle graph
In the mathematical field of graph theory, the triangle graph is a planar undirected graph with 3 vertices and 3 edges, in the form of a triangle. The triangle graph is also known as the cycle graph a
Franklin graph
In the mathematical field of graph theory, the Franklin graph is a 3-regular graph with 12 vertices and 18 edges. The Franklin graph is named after Philip Franklin, who disproved the Heawood conjectur
Heawood graph
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.
Vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G in which, given any two vertices v1 and v2 of G, there is some automorphism such that In other words, a graph is verte
Wells graph
The Wells graph is the unique distance-regular graphwith intersection array .. Its spectrum is. Its queue number is 3 and its upper bound on the book thickness is 5.
Suzuki graph
The Suzuki graph is a strongly regular graph with parameters . Its automorphism group has order 896690995200 and contains as a subgroup of order 2 the Suzuki sporadic group. It is named for Michio Suz
Chvátal graph
In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal. It is triangle-free: its girth (the length of its short
Flower snark
In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975. As snarks, the flower snarks are connected, bridgeless cubic graphs w
Balaban 11-cage
In the mathematical field of graph theory, the Balaban 11-cage or Balaban (3,11)-cage is a 3-regular graph with 112 vertices and 168 edges named after Alexandru T. Balaban. The Balaban 11-cage is the
Symmetric graph
In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism such that and In other
Walk-regular graph
In discrete mathematics, a walk-regular graph is a simple graph where the number of closed walks of any length from a vertex to itself does not depend on the choice of vertex.
Brinkmann graph
In the mathematical field of graph theory, the Brinkmann graph is a 4-regular graph with 21 vertices and 42 edges discovered by Gunnar Brinkmann in 1992. It was first published by Brinkmann and Mering
Gosset graph
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.
Nauru graph
In the mathematical field of graph theory, the Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag
Laves graph
In geometry and crystallography, the Laves graph is an infinite and highly symmetric system of points and line segments in three-dimensional Euclidean space, forming a periodic graph. Three equal-leng
Blanuša snarks
In the mathematical field of graph theory, the Blanuša snarks are two 3-regular graphs with 18 vertices and 27 edges. They were discovered by Yugoslavian mathematician Danilo Blanuša in 1946 and are n
Higman–Sims graph
In mathematical graph theory, the Higman–Sims graph is a 22-regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pai
Platonic graph
In the mathematical field of graph theory, a Platonic graph is a graph that has one of the Platonic solids as its skeleton. There are 5 Platonic graphs, and all of them are regular, polyhedral (and th
Diamond cubic
The diamond cubic crystal structure is a repeating pattern of 8 atoms that certain materials may adopt as they solidify. While the first known example was diamond, other elements in group 14 also adop
Holt graph
In graph theory, the Holt graph or Doyle graph is the smallest half-transitive graph, that is, the smallest example of a vertex-transitive and edge-transitive graph which is not also symmetric. Such g
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
Desargues graph
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 co
Hall–Janko graph
In the mathematical field of graph theory, the Hall–Janko graph, also known as the Hall-Janko-Wales graph, is a 36-regular undirected graph with 100 vertices and 1800 edges. It is a rank 3 strongly re
Shuffle-exchange network
In graph theory, the shuffle-exchange network is an undirected cubic multigraph, whose vertices represent binary sequences of a given length and whose edges represent two operations on these sequence,
Circular coloring
In graph theory, circular coloring is a kind of coloring that may be viewed as a refinement of the usual graph coloring. The circular chromatic number of a graph , denoted can be given by any of the f
Random regular graph
A random r-regular graph is a graph selected from , which denotes the probability space of all r-regular graphs on vertices, where and is even. It is therefore a particular kind of random graph, but t
Barnette–Bosák–Lederberg graph
In the mathematical field of graph theory, the Barnette–Bosák–Lederberg graph is a cubic (that is, 3-regular) polyhedral graph with no Hamiltonian cycle, the smallest such graph possible. It was disco
Distance-transitive graph
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance,
Foster cage
In the mathematical field of graph theory, the Foster cage is a 5-regular undirected graph with 30 vertices and 75 edges. It is one of the four (5,5)-cage graphs, the others being the Meringer graph,
Grassmann graph
In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph Jq(n, k) are the k-dimensional subspaces of an n-dimension
Meredith graph
In the mathematical field of graph theory, the Meredith graph is a 4-regular undirected graph with 70 vertices and 140 edges discovered by Guy H. J. Meredith in 1973. The Meredith graph is 4-vertex-co
Bidiakis cube
In the mathematical field of graph theory, the Bidiakis cube is a 3-regular graph with 12 vertices and 18 edges.
Livingstone graph
In the mathematical field of graph theory, the Livingstone graph is a distance-transitive graph with 266 vertices and 1463 edges. Its intersection array is {11,10,6,1;1,1,5,11}. It is the largest dist
Circulant graph
In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has
Möbius–Kantor graph
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 b
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 gra
Harries–Wong graph
In the mathematical field of graph theory, the Harries–Wong graph is a 3-regular undirected graph with 70 vertices and 105 edges. The Harries–Wong graph has chromatic number 2, chromatic index 3, radi
Gewirtz graph
The Gewirtz graph is a strongly regular graph with 56 vertices and valency 10. It is named after the mathematician Allan Gewirtz, who described the graph in his dissertation.
Tietze's graph
In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges.It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbi
Moore graph
In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a grap
F26A graph
In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges. It has chromatic number 2, chromatic index 3, diameter 5, radius 5 and gir
Szekeres snark
In the mathematical field of graph theory, the Szekeres snark is a snark with 50 vertices and 75 edges. It was the fifth known snark, discovered by George Szekeres in 1973. As a snark, the Szekeres gr
Folded cube 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.
Foster graph
In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges. The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3
Horton graph
In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it
Dejter graph
In the mathematical field of graph theory, the Dejter graph is a 6-regular graph with 112 vertices and 336 edges. The Dejter graph isobtained by deleting a copyof the Hamming code of length 7 from the
Schläfli graph
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 paramet
Utility graph
No description available.
Kneser graph
In graph theory, the Kneser graph K(n, k) (alternatively KGn,k) is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only
Zero-symmetric graph
In the mathematical field of graph theory, a zero-symmetric graph is a connected graph in which each vertex has exactly three incident edges and, for each two vertices, there is a unique symmetry taki
Odd graph
In the mathematical field of graph theory, the odd graphs On are a family of symmetric graphs with high odd girth, defined from certain set systems. They include and generalize the Petersen graph.
Perkel graph
In mathematics, the Perkel graph, named after Manley Perkel, is a 6-regular graph with 57 vertices and 171 edges. It is the unique distance-regular graph with intersection array (6, 5, 2; 1, 1, 3). Th
Ljubljana graph
In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges. It is a cubic graph with diameter 8, radius 7, chromatic number 2 and c
Markström graph
No description available.
Frankl–Rödl graph
In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other. The gr
Generalized Petersen graph
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the P
Folkman graph
In the mathematical field of graph theory, the Folkman graph is a 4-regular graph with 20 vertices and 40 edges. It is a regular bipartite graph with symmetries taking every edge to every other edge,
Ramanujan graph
In the mathematical field of spectral graph theory, a Ramanujan graph is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectr
Thomsen graph
No description available.
McKay–Miller–Širáň graph
In graph theory, the McKay–Miller–Širáň graphs are an infinite class of vertex-transitive graphs with diameter two, and with a large number of vertices relative to their diameter and degree. They are
Rook's graph
In graph theory, a rook's graph is a 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 each edge con
Paley graph
In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs fo
Hamming graph
Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) and computer science. Let S be a set of q elements and d a positive
Robertson graph
In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4-regular undirected graph with 19 vertices and 38 edges named after Neil Robertson. The Robertson graph is the uniqu
Harborth graph
No description available.
Distance-regular graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depe
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 stronge
Shrikhande graph
In the mathematical field of graph theory, the Shrikhande graph is a named graph discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex
In graph theory, the Möbius ladder Mn, for even numbers n, is formed from an n-cycle by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a cubic, circulant graph
Table of simple cubic graphs
The connected 3-regular (cubic) simple graphs are listed for small vertex numbers.
Biggs–Smith graph
In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges. It has chromatic number 3, chromatic index 3, radius 7, diameter 7 and girth 9. I
McGee graph
In the mathematical field of graph theory, the McGee graph or the (3-7)-cage is a 3-regular graph with 24 vertices and 36 edges. The McGee graph is the unique (3,7)-cage (the smallest cubic graph of g
Double-star snark
In the mathematical field of graph theory, the double-star snark is a snark with 30 vertices and 45 edges. In 1975, Rufus Isaacs introduced two infinite families of snarks—the flower snark and the , a
Harries graph
In the mathematical field of graph theory, the Harries graph or Harries (3-10)-cage is a 3-regular, undirected graph with 70 vertices and 105 edges. The Harries graph has chromatic number 2, chromatic
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent
110-vertex Iofinova-Ivanov graph
The 110-vertex Iofinova-Ivanov graph is, in graph theory, a semi-symmetric cubic graph with 110 vertices and 165 edges.
Balaban 10-cage
In the mathematical field of graph theory, the Balaban 10-cage or Balaban (3,10)-cage is a 3-regular graph with 70 vertices and 105 edges named after Alexandru T. Balaban. Published in 1972, It was th
Cameron graph
The Cameron graph is a strongly regular graph of parameters .
Halved cube graph
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 hyperc
Ellingham–Horton graph
In the mathematical field of graph theory, the Ellingham–Horton graphs are two 3-regular graphs on 54 and 78 vertices: the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named a
Crown graph
In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices {u1, u2, …, un} and {v1, v2, …, vn} and with an edge from ui to vj whenever i ≠
Prism graph
In the mathematical field of graph theory, a prism graph is a graph that has one of the prisms as its skeleton.
Archimedean graph
In the mathematical field of graph theory, an Archimedean graph is a graph that forms the skeleton of one of the Archimedean solids. There are 13 Archimedean graphs, and all of them are regular, polyh