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
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
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