Graph Classes & Invariants¶

← Back to Domain-Specific Families

Abstractions that classify graphs by structural constraints — regularity, degree sequences, cliques, symmetry, connectivity — and define numeric invariants such as degeneracy, domatic number, rank-width, and Zagreb indices, or construction operations like Cartesian products, clique-sums, and local complementation.

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

(a, b)-decomposition — An (a, b)-decomposition assigns a graph's edges to a specified number a of forest parts and one residual part of maximum degree at most b.
Adjacency list — A graph representation that associates each vertex with a collection of its neighboring vertices or incident edges.
Asymmetric graph — A graph whose automorphism group is trivial, so no nonidentity permutation of vertices preserves adjacency.
Block Graph — is a type of undirected graph in which every biconnected component (block) is a clique.
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.
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.
Cubic Graph — A graph in which every vertex has degree exactly three, creating a sparse regular class with distinctive matching, coloring, symmetry, and Hamiltonicity theory.
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.
Domatic number — Assign a graph the largest number of blocks in a vertex partition for which every block is a dominating set.
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.
Friendly-index set — Collect every edge-label imbalance attainable from nearly balanced binary vertex labelings of a graph, yielding a set-valued graph invariant rather than one selected labeling.
Graph bandwidth — The minimum possible largest label distance across an edge when a graph’s vertices are placed at distinct positions on a line.
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 Vertex — In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.
Haven (Graph Theory) — Assign every deletion set smaller than a stated order to a surviving connected component in a nested or pairwise-touching way, certifying an evader's coherent refuge and dualizing bounded treewidth.
Highly irregular graph — A graph in which the neighbors of every vertex all have pairwise distinct degrees.
Hosoya Index — Count every matching of a graph, including the empty matching, to obtain a graph invariant used in matching theory and as a molecular topological descriptor.
Labeled graph — A graph equipped with one or more functions assigning labels from declared sets to vertices, edges, or both, under explicit semantic and constraint conventions.
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.
N-flake — Generate a family of polygonal self-similar attractors by placing contracted copies of a regular n-gon at its vertices, optionally adding a convention-controlled central copy, and iterating the resulting similarity system.
Partial cube — A graph that embeds isometrically into a hypercube, equivalently admitting equal-length bit labels whose Hamming distances exactly equal graph distances.
Quartic graph — A graph in which every vertex has degree four, also called a 4-regular graph.
Random graph theory of gelation — A polymer-network theory representing multifunctional monomers and their bonds as random graphs so giant-component emergence marks the gel point.
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.
Roman Dominating Set — A graph labeling assigns each vertex 0, 1, or 2 so every zero vertex neighbors a two vertex; the least total label weight is its Roman domination number.
Semi-symmetric graph — A regular undirected graph whose automorphism group is transitive on edges but not on vertices.
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.
Strongly regular graph — A regular graph with fixed numbers of common neighbors for every adjacent pair and for every nonadjacent pair, summarized by parameters (v,k,lambda,mu).
Zagreb indices — Degree-based graph invariants, especially sums of squared vertex degrees or products of endpoint degrees, originally used as molecular topological descriptors.