- Combinatorics
- >
- Graph theory
- >
- Graphs
- >
- Graph families

- Discrete mathematics
- >
- Graph theory
- >
- Graphs
- >
- Graph families

- Fields of mathematics
- >
- Graph theory
- >
- Graphs
- >
- Graph families

- Mathematical relations
- >
- Graph theory
- >
- Graphs
- >
- Graph families

- Theoretical computer science
- >
- Graph theory
- >
- Graphs
- >
- Graph families

Medial graph

In the mathematical discipline of graph theory, the medial graph of plane graph G is another graph M(G) that represents the adjacencies between edges in the faces of G. Medial graphs were introduced i

Parity graph

In graph theory, a parity graph is a graph in which every two induced paths between the same two vertices have the same parity: either both paths have odd length, or both have even length. This class

List of graphs by edges and vertices

This sortable list points to the articles describing various individual (finite) graphs. The columns 'vertices', 'edges', 'radius', 'diameter', 'girth', 'P' (whether the graph is planar), χ (chromatic

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following w

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

Apollonian network

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently

Extractor (mathematics)

An -extractor is a bipartite graph with nodes on the left and nodes on the right such that each node on the left has neighbors (on the right), which has the added property thatfor any subset of the le

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

List of graphs

This partial list of graphs contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own. For collected definitions of graph

Skew-symmetric graph

In graph theory, a branch of mathematics, a skew-symmetric graph is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism

Implication graph

In mathematical logic and graph theory, an implication graph is a skew-symmetric, directed graph G = (V, E) composed of vertex set V and directed edge set E. Each vertex in V represents the truth stat

Panconnectivity

In graph theory, a panconnected graph is an undirected graph in which, for every two vertices s and t, there exist paths from s to t of every possible length from the distance d(s,t) up to n − 1, wher

Outerplanar graph

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagne

Cop-win graph

In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit–evasion game against a robber, with the players taking alternating turns in which they can c

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

Subhamiltonian graph

In graph theory and graph drawing, a subhamiltonian graph is a subgraph of a planar Hamiltonian graph.

Bipartite graph

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is every edge connects a vertex in

Descartes snark

In the mathematical field of graph theory, a Descartes snark is an undirected graph with 210 vertices and 315 edges. It is a snark, first discovered by William Tutte in 1948 under the pseudonym Blanch

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.

Common graph

In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, is a common graph if it "commonl

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

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

Factor-critical graph

In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph) is a graph with n vertices in which every subgraph of n − 1 vertices has a perfect matching. (A perfect mat

Lattice graph

In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformation

Homogeneous graph

In mathematics, a k-ultrahomogeneous graph is a graph in which every isomorphism between two of its induced subgraphs of at most k vertices can be extended to an automorphism of the whole graph. A k-h

Contact graph

In the mathematical area of graph theory, a contact graph or tangency graph is a graph whose vertices are represented by geometric objects (e.g. curves, line segments, or polygons), and whose edges co

Multipartite graph

In graph theory, a part of mathematics, a k-partite graph is a graph whose vertices are (or can be) partitioned into k different independent sets. Equivalently, it is a graph that can be colored with

Quasi-bipartite graph

In the mathematical field of graph theory, an instance of the Steiner tree problem (consisting of an undirected graph G and a set R of terminal vertices that must be connected to each other) is said t

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

Convex bipartite graph

In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties.A bipartite graph, (U ∪ V, E), is said to be convex over the vertex set U if U can be

Reeb graph

A Reeb graph (named after Georges Reeb by René Thom) is a mathematical object reflecting the evolution of the level sets of a real-valued function on a manifold.According to a similar concept was intr

Median graph

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths betwe

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").

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

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.

Trivially perfect graph

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially pe

Well-colored graph

In graph theory, a subfield of mathematics, a well-colored graph is an undirected graph for which greedy coloring uses the same number of colors regardless of the order in which colors are chosen for

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 w

Gallery of named graphs

Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concret

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

Hypohamiltonian graph

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonia

Leaf power

In the mathematical area of graph theory, a k-leaf power of a tree T is a graph G whose vertices are the leaves of T and whose edges connect pairs of leaves whose distance in T is at most k. That is,

Block graph

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique. Block graphs are sometimes

Self-complementary graph

In the mathematical field of graph theory, a self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the 4-vertex path graph a

Expander graph

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure

Polytope graph

No description available.

K-edge-connected graph

In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed. The edge-connectivity of a graph is the largest k for which the graph is k-edge-

Cayley graph

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested

Scale-free network

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes fo

Distance-hereditary graph

In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the sa

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,

Comparability graph

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitiv

Dually chordal graph

In the mathematical area of graph theory, an undirected graph G is dually chordal if the hypergraph of its maximal cliques is a hypertree. The name comes from the fact that a graph is chordal if and o

Apex graph

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the

Asymmetric graph

In graph theory, a branch of mathematics, an undirected graph is called an asymmetric graph if it has no nontrivial symmetries. Formally, an automorphism of a graph is a permutation p of its vertices

Disperser

A disperser is a one-sided extractor. Where an extractor requires that every event gets the same probability under the uniform distribution and the extracted distribution, only the latter is required

Meyniel graph

In graph theory, a Meyniel graph is a graph in which every odd cycle of length five or more has at least two chords (edges connecting non-consecutive vertices of the cycle). The chords may be uncrosse

Modular graph

In graph theory, a branch of mathematics, the modular graphs are undirected graphs in which every three vertices x, y, and z have at least one median vertex m(x, y, z) that belongs to shortest paths b

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

Aperiodic graph

In the mathematical area of graph theory, a directed graph is said to be aperiodic if there is no integer k > 1 that divides the length of every cycle of the graph. Equivalently, a graph is aperiodic

Halin graph

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle.The tree must have at least four vertices, none of which has exactly two neighbors

Word-representable graph

In the mathematical field of graph theory, a word-representable graph is a graph that can be characterized by a word (or sequence) whose entries alternate in a prescribed way. In particular, if the ve

Cactus graph

In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every e

Split graph

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer ,

Line graph of a hypergraph

In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraph H, denoted L(H), is the graph whose vertex set is the set of the hyperedges of H, with two vertices adjacent

Bound graph

In graph theory, a bound graph expresses which pairs of elements of some partially ordered set have an upper bound. Rigorously, any graph G is a bound graph if there exists a partial order ≤ on the ve

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

Ptolemaic graph

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Pto

Biconnected graph

In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no a

Simplex graph

In graph theory, a branch of mathematics, the simplex graph κ(G) of an undirected graph G is itself a graph, with one node for each clique (a set of mutually adjacent vertices) in G. Two nodes of κ(G)

Cluster graph

In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs.Equivalently, a graph is a cluster graph if and only if it has no three-vertex in

Laman graph

In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on n vertices such that, for

Pairwise compatibility graph

In graph theory, a graph is a pairwise compatibility graph (PCG) if there exists a tree and two non-negative real numbers such that each node of has a one-to-one mapping with a leaf node of such that

Partial k-tree

In graph theory, a partial k-tree is a type of graph, defined either as a subgraph of a k-tree or as a graph with treewidth at most k. Many NP-hard combinatorial problems on graphs are solvable in pol

Biased graph

In mathematics, a biased graph is a graph with a list of distinguished circles (edge sets of simple cycles), such that if two circles in the list are contained in a theta graph, then the third circle

K-tree

In graph theory, a k-tree is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex v has exactly k neighb

Toroidal graph

In the mathematical field of graph theory, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.

Petersen family

In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6. The Petersen family is named after Danish mathematician Julius Pete

Threshold graph

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations: 1.
* Addition of a single isolated vertex to th

Forcing graph

In graph theory, a forcing graph is one whose density determines whether a graph sequence is quasi-random. The term was first coined by Chung, Graham, and Wilson in 1989., and forcing graphs play an i

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

Lévy family of graphs

In graph theory, a branch of mathematics, a Lévy family of graphs is a family of graphs Gn, n = 1, 2, 3, ..., which possess a certain type of "compactness" or "tangledness". Many naturally occurring f

Critical graph

In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deleti

Even-hole-free graph

In the mathematical area of graph theory, a graph is even-hole-free if it contains no induced cycle with an even number of vertices. demonstrated that every even-hole-free graph contains a , which set

Highly irregular graph

In graph theory, a highly irregular graph is a graph in which, for every vertex, all neighbors of that vertex have distinct degrees.

Linear forest

In graph theory, a branch of mathematics, a linear forest is a kind of forest formed from the disjoint union of path graphs. It is an undirected graph with no cycles in which every vertex has degree a

Hanan grid

In geometry, the Hanan grid H(S) of a finite set S of points in the plane is obtained by constructing vertical and horizontal lines through each point in S. The main motivation for studying the Hanan

Partial cube

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 distan

Biclique-free graph

In graph theory, a branch of mathematics, a t-biclique-free graph is a graph that has no 2t-vertex complete bipartite graph Kt,t as a subgraph. A family of graphs is biclique-free if there exists a nu

Pancyclic graph

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph.

K-vertex-connected graph

In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed. The vertex-conne

Overfull graph

In graph theory, an overfull graph is a graph whose size is greater than the product of its maximum degree and half of its order floored, i.e. where is the size of G, is the maximum degree of G, and i

Integral graph

In the mathematical field of graph theory, an integral graph is a graph whose adjacency matrix's spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the root

Kronecker graph

Kronecker graphs are a construction for generating graphs for modeling systems. The method constructs a sequence of graphs from a small base graph by iterating the Kronecker product. A variety of gene

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can

Cograph

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family

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

Bivariegated graph

In graph theory, a bivariegated graph is a graph whose vertex set can be partitioned into two equal parts such that each vertex is adjacent to exactly one vertex from the other set not containing it.I

Pseudoforest

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that n

Claw-free graph

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star gr

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

Geodetic graph

In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices. Geodetic graphs were introduced in 1962 by Øystein Ore, w

Chordal graph

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of

Well-covered graph

In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all

Map graph

In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane.

Series–parallel graph

In graph theory, series–parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and paral

Conference graph

In the mathematical area of graph theory, a conference graph is a strongly regular graph with parameters v, k = (v − 1)/2, λ = (v − 5)/4, and μ = (v − 1)/4. It is the graph associated with a symmetric

Universal graph

In mathematics, a universal graph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard R

Chordal bipartite graph

In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertice

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

Locally linear graph

In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exact

Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from t

Domination perfect graph

No description available.

Strongly chordal graph

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length (≥ 6) in G has an odd chord, i.e., an edge that connects two

Prism graph

In the mathematical field of graph theory, a prism graph is a graph that has one of the prisms as its skeleton.

Squaregraph

In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with thre

Strangulated graph

In graph theoretic mathematics, a strangulated graph is a graph in which deleting the edges of any induced cycle of length greater than three would disconnect the remaining graph. That is, they are th

Dense graph

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a

Small-world network

A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes

Edge-transitive graph

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. In other words, a grap

© 2023 Useful Links.