Graph Theory¶

← Back to Domain-Specific Abstractions by Domain

60 domain-specific abstractions whose origin domain is Graph Theory.

Apollonian network — A recursively generated planar graph formed by repeatedly inserting a vertex into a triangular face and joining it to that face’s three vertices.
Asymmetric graph — A graph whose automorphism group is trivial, so no nonidentity permutation of vertices preserves adjacency.
Biclique-free graph — A graph excluding some fixed complete bipartite graph as a subgraph.
Biregular graph — A bipartite graph in which all vertices on each side have one common degree, with the two sides allowed different degrees.
Bivariegated graph — An even-order graph whose vertices split into equal parts so every vertex has exactly one neighbor across the split.
Cartesian product of graphs — Construct a graph on ordered vertex pairs in which an edge changes exactly one coordinate along an edge of its corresponding factor while holding the other coordinate fixed.
Claw-free graph — A graph containing no induced subgraph isomorphic to the four-vertex star K1,3.
Clique graph — Transform an undirected graph into the intersection graph of its maximal cliques, making each maximal clique a vertex and joining two when their underlying vertex sets intersect.
Clique-sum — Combine graphs by choosing equally sized complete subgraphs, identifying their vertices through a bijection, and optionally deleting interface-clique edges under an explicit convention.
Clique-width — The minimum number of labels needed to construct a graph by vertex creation, disjoint union, complete joins between labels, and relabeling.
Cograph — A graph generated from single vertices by repeated disjoint union and complementation, equivalently a graph with no induced four-vertex path and a recursive cotree decomposition.
Component (graph theory) — A maximal connected subgraph of an undirected graph; the graph's components uniquely partition its vertex set.
Cop number — The minimum number of pursuers required to guarantee capture of an evader in the standard cops-and-robber game on a graph.
Corona product — A graph operation joining each vertex of one graph to every vertex of its own attached copy of a second graph.
Cyclomatic number — The dimension of an undirected graph's cycle space, equal to the minimum number of edges whose removal makes it acyclic and computed as edges minus vertices plus connected components.
Deficiency (graph theory) — A matching-theoretic shortfall measure, commonly the maximum over vertex subsets of the number of selected vertices minus the size of their neighborhood.
Degeneracy (graph theory) — The least k such that every nonempty subgraph has a vertex of degree at most k, equivalently the maximum core number in a graph.
Degree (graph theory) — The number of edge ends incident to a vertex, with loops counted twice in an undirected multigraph and distinct in-degree and out-degree counts for directed graphs.
Diameter (graph theory) — Measure a connected graph by the maximum shortest-path distance over all pairs of vertices.
Distance (graph theory) — The length of a shortest path between two graph vertices, with infinity or undefined value when no admissible path connects them.
Domatic number — Assign a graph the largest number of blocks in a vertex partition for which every block is a dominating set.
Dually chordal graph — A graph admitting a maximum-neighborhood ordering, equivalently one whose maximal-clique hypergraph has a join tree with the graph’s vertex set as host.
Entanglement (graph measure) — A directed-graph complexity measure equal to the least number of cops needed to capture a perpetually moving robber in the entanglement game.
Equitable coloring — A proper vertex coloring whose color classes differ in size by at most one, combining adjacency separation with balanced allocation.
Expander graph — A sparse finite graph in which every not-too-large vertex set has a proportionally large boundary, equivalently exhibiting strong combinatorial or spectral expansion.
Factor-critical graph — An odd-order graph in which deleting any single vertex leaves a graph with a perfect matching, equivalently every vertex can be the unmatched vertex of a near-perfect matching.
Fibrations of graphs — Directed-graph homomorphisms with a unique lifting property for incoming edges, making each base edge lift uniquely to every vertex over its target.
Gallai–Hasse–Roy–Vitaver theorem — A graph-theoretic duality stating that a graph's chromatic number equals one plus the minimum, over all edge orientations, of the longest directed-path length.
Goldberg–Seymour Theorem — Every loopless multigraph can be properly edge-colored using no more than the larger of maximum degree plus one and the ceiling of its densest odd-set edge ratio.
Graph factorization — A decomposition of a graph's edge set into spanning regular subgraphs called factors, with a k-factorization partitioning all edges into k-regular factors.
Graph isomorphism — A bijection between two graph vertex sets that preserves adjacency and nonadjacency, showing that the graphs have the same structure up to relabeling.
Hajós construction — A graph-composition operation that deletes one edge from each of two graphs, identifies selected endpoints and joins the remaining endpoints.
Highly irregular graph — A graph in which the neighbors of every vertex all have pairwise distinct degrees.
Homeomorphism (graph theory) — The equivalence of graphs that become isomorphic after subdividing edges by degree-two vertices.
Independent set (graph theory) — A vertex subset of a graph in which no two selected vertices are adjacent.
Intersection graph — A graph representing a family of sets or objects, with one vertex per object and an edge exactly when the corresponding pair intersects.
Intersection number (graph theory) — The minimum ground-set size needed to represent a graph as intersections among finite vertex-associated sets, equivalently its minimum edge-clique cover size.
Join (graph theory) — A graph operation that takes two disjoint graphs and adds every possible edge between their vertex sets while retaining their internal edges.
Lattice graph — Represent a regular Euclidean lattice or tiling by vertices at lattice sites and edges joining sites under a fixed local-neighbor rule.
Local complementation — A graph operation that toggles every adjacency among neighbors of a selected vertex while leaving the selected vertex and all other adjacencies unchanged.
Matching (graph theory) — A set of graph edges with no shared endpoint.
Orientation (graph theory) — An assignment of one direction to every edge of an undirected graph, producing a directed graph with the same vertices and underlying edges.
Pancyclic graph — A graph containing a cycle of every length from three through its number of vertices.
Partial cube — A graph that embeds isometrically into a hypercube, equivalently admitting equal-length bit labels whose Hamming distances exactly equal graph distances.
Path coloring — An assignment of colors to specified graph paths so any two paths sharing an edge receive different colors, commonly modeling wavelength allocation in optical networks.
Quartic graph — A graph in which every vertex has degree four, also called a 4-regular graph.
Rainbow coloring — An edge coloring of a connected graph in which every pair of vertices is joined by a path whose edges all have distinct colors.
Random graph — A graph-valued random object specified by a probability distribution or stochastic generation rule over vertices and edges.
Rank-width — A graph width parameter that minimizes, over subcubic decomposition trees, the maximum binary rank of the adjacency matrix crossing any induced vertex cut.
Reconstruction conjecture — The conjecture that every finite simple graph with at least three vertices is determined up to isomorphism by the multiset of its vertex-deleted subgraphs.
Self-complementary graph — A graph isomorphic to its complement, so some vertex relabeling exchanges edges with nonedges while preserving graph structure.
Semi-symmetric graph — A regular undirected graph whose automorphism group is transitive on edges but not on vertices.
Signed graph — A graph whose edges carry positive or negative signs, with cycle-sign products determining balance and switching equivalence.
Snark (graph theory) — A connected cubic graph whose edges cannot be properly colored with three colors, usually restricted by girth and nontrivial connectivity conditions.
Split graph — A graph whose vertices can be partitioned into one clique and one independent set.
Starlike tree — A tree with exactly one vertex of degree greater than two, equivalently several paths joined at one central vertex.
Strength of a graph — A graph-connectivity invariant given by the minimum ratio of removed edges to the number of additional components they create, equivalently a minimum partition cut ratio.
Transitive reduction — A smallest-edge directed graph preserving exactly the reachability relation of a given directed graph.
Triangle-free graph — An undirected graph containing no cycle of length three, equivalently no three-vertex clique.
Zero-symmetric graph — A connected cubic graph whose automorphism group acts regularly on vertices but is not transitive on edges.