Category: Parametric families of graphs

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
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
Andrásfai graph
In graph theory, an Andrásfai graph is a triangle-free, circulant graph named after Béla Andrásfai.
Henson graph
In graph theory, the Henson graph Gi is an undirected infinite graph, the unique countable homogeneous graph that does not contain an i-vertex clique but that does contain all Ki-free finite graphs as
Bouquet graph
In mathematics, a bouquet graph , for an integer parameter , is an undirected graph with one vertex and edges, all of which are self-loops. It is the graph-theoretic analogue of the topological bouque
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
Fibonacci cube
In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathemat
Hedgehog (hypergraph)
In the mathematical theory of hypergraphs, a hedgehog is a 3-uniform hypergraph defined from an integer parameter . It has vertices, of which can be labeled by the integers from to and the remaining o
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
King's graph
In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move.
Friendship graph
In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or n-fan) Fn is a planar, undirected graph with 2n + 1 vertices and 3n edges. The friendship graph Fn can be co
Knight's graph
In graph theory, a knight's graph, or a knight's tour graph, is a graph that represents all legal moves of the knight chess piece on a chessboard. Each vertex of this graph represents a square of the
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
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
Lollipop graph
In the mathematical discipline of graph theory, the (m,n)-lollipop graph is a special type of graph consisting of a complete graph (clique) on m vertices and a path graph on n vertices, connected with
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
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
Nested triangles graph
In graph theory, a nested triangles graph with n vertices is a planar graph formed from a sequence of n/3 triangles, by connecting pairs of corresponding vertices on consecutive triangles in the seque
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
Turán graph
The Turán graph, denoted by , is a complete multipartite graph; it is formed by partitioning a set of vertices into subsets, with sizes as equal as possible, and then connecting two vertices by an edg
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
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
Möbius ladder
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
Path graph
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order v1, v2, …, vn such that the edges are {vi, vi+1} where i = 1, 2, …, n − 1.
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.
Hanoi graph
In graph theory and recreational mathematics, the Hanoi graphs are undirected graphs whose vertices represent the possible states of the Tower of Hanoi puzzle, and whose edges represent allowable move
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second se
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
Ladder graph
In the mathematical field of graph theory, the ladder graph Ln is a planar, undirected graph with 2n vertices and 3n – 2 edges. The ladder graph can be obtained as the Cartesian product of two path gr
Queen's graph
In mathematics, a queen's graph is a graph that represents all legal moves of the queen—a chess piece—on a chessboard. In the graph, each vertex represents a square on a chessboard, and each edge is a
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
Tadpole graph
In the mathematical discipline of graph theory, the (m,n)-tadpole graph is a special type of graph consisting of a cycle graph on m (at least 3) vertices and a path graph on n vertices, connected with
De Bruijn graph
In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences
Kautz graph
The Kautz graph is a directed graph of degree and dimension , which has vertices labeled by allpossible strings of length which are composed of characters chosen froman alphabet containing distinctsym
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
Book (graph theory)
In graph theory, a book graph (often written ) may be any of several kinds of graph formed by multiple cycles sharing an edge.
Cocktail party graph
No description available.
Windmill graph
In the mathematical field of graph theory, the windmill graph Wd(k,n) is an undirected graph constructed for k ≥ 2 and n ≥ 2 by joining n copies of the complete graph Kk at a shared universal vertex.
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
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,
Pancake graph
In the mathematical field of graph theory, the pancake graph Pn or n-pancake graph is a graph whose vertices are the permutations of n symbols from 1 to n and its edges are given between permutations
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.
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 ≠
Keller's conjecture
In geometry, Keller's conjecture is the conjecture that in any tiling of n-dimensional Euclidean space by identical hypercubes, there are two hypercubes that share an entire (n − 1)-dimensional face w
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
Half graph
In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bip
Star (graph theory)
In graph theory, a star Sk is the complete bipartite graph K1,k : a tree with one internal node and k leaves (but no internal nodes and k + 1 leaves when k ≤ 1). Alternatively, some authors define Sk
Wheel graph
In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as
Barbell graph
In the mathematical discipline of graph theory, the n-barbell graph is a special type of undirected graph consisting of two non-overlapping n-vertex cliques together with a single edge that has an end
Shannon multigraph
In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by , are a special type of triangle graphs, which are used in the field of edge coloring in particular.