Graph Invariants & Constructions

← Back to Domain-Specific Families

Abstractions about constructing, transforming, and classifying graphs through connectivity, products, crossings, matchings, domination, planarity, and numerical invariants. They capture structural restrictions and measures that distinguish graph families or govern graph algorithms.

49 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Ancestral graph — A mixed graph using directed, bidirected and undirected edges to encode conditional independences left by latent-variable marginalization and selection conditioning in a DAG.
• 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.
• Bidimensionality — A graph-algorithm framework for parameters that grow quadratically on grid-like graphs and do not increase under minors or contractions, enabling subexponential and kernel results.
• 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.
• Clique-width — The minimum number of labels needed to construct a graph by vertex creation, disjoint union, complete joins between labels, and relabeling.
• Colin de Verdière graph invariant — A minor-monotone graph parameter defined by the maximum corank of a constrained symmetric matrix with one negative eigenvalue and the Strong Arnold property.
• Conductance (graph theory) — A normalized bottleneck measure comparing the edge flow leaving a vertex set with the smaller stationary volume of that set and its complement.
• Cop number — The minimum number of pursuers required to guarantee capture of an evader in the standard cops-and-robber game on a graph.
• Cop-win graph — A graph on which one pursuer has a strategy that guarantees capture of one evader in the alternating vertex-movement game.
• Corona product — A graph operation joining each vertex of one graph to every vertex of its own attached copy of a second graph.
• Crossing number (graph theory) — The minimum number of edge intersections over all plane drawings of a graph under a specified crossing convention.
• 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.
• 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.
• Dissociation number — The maximum number of vertices in a graph whose induced subgraph has maximum degree at most one.
• Distance (graph theory) — The length of a shortest path between two graph vertices, with infinity or undefined value when no admissible path connects them.
• Double graph — A graph construction that replaces every vertex with two nonadjacent copies and replaces each original edge with all four edges between the corresponding copy pairs.
• Eternal dominating set — A set of graph vertices occupied by mobile guards that can respond to every infinite sequence of vertex attacks while remaining a dominating set after each move.
• Factor graph — A bipartite graph whose variable nodes and factor nodes expose how a multivariate function decomposes into local functions.
• 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.
• Graph rewriting — Rule-based transformation of a host graph by matching a left-hand pattern and replacing or relinking it according to a right-hand graph.
• Hajós construction — A graph-composition operation that deletes one edge from each of two graphs, identifies selected endpoints and joins the remaining endpoints.
• 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.
• Integral graph — A finite graph whose adjacency matrix has only integer eigenvalues.
• 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.
• Line graph of a hypergraph — The graph whose vertices are a hypergraph’s hyperedges and whose adjacency records nonempty intersection between the corresponding hyperedges.
• Map graph — The intersection graph of finitely many interior-disjoint simply connected regions in the plane, with vertices for regions and adjacency whenever two regions meet at any boundary point.
• Matching (graph theory) — A set of graph edges with no shared endpoint.
• Modular graph — An undirected graph in which every triple of vertices has at least one common median lying on a shortest path between each pair.
• 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.
• Planarity testing — The algorithmic decision problem of determining whether a graph admits a crossing-free plane embedding and producing either an embedding or an obstruction.
• Randić index — A graph invariant summing the reciprocal square root of endpoint-degree products over all edges, widely used as a molecular connectivity descriptor.
• Self-complementary graph — A graph isomorphic to its complement, so some vertex relabeling exchanges edges with nonedges while preserving graph structure.
• 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.
• Strong product of graphs — A graph product on ordered vertex pairs where two pairs are adjacent when their first coordinates are equal or adjacent and independently their second coordinates are equal or adjacent, excluding equality in both.
• Thickness (graph theory) — The minimum number of planar spanning subgraphs needed to partition a graph's edge set.
• Triangle-free graph — An undirected graph containing no cycle of length three, equivalently no three-vertex clique.
• Unit disk graph — The intersection graph of equal-radius disks in the Euclidean plane, equivalently a graph connecting points whose pairwise distance is at most a fixed threshold after scaling.
• Wiener index — The sum of shortest-path distances over all unordered vertex pairs of a connected graph.
• Zagreb indices — Degree-based graph invariants, especially sums of squared vertex degrees or products of endpoint degrees, originally used as molecular topological descriptors.
• Zero-symmetric graph — A connected cubic graph whose automorphism group acts regularly on vertices but is not transitive on edges.