- Graph theory
- >
- Graphs
- >
- Graph families
- >
- 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.

© 2023 Useful Links.