Graph Theory Structures & Invariants

← Back to Domain-Specific Families

Abstractions that define graph classes, operations and structural invariants, including planarity, treewidth, clique-width and crossing number, spanning graph products, colorings, matchings and connectivity measures used to classify and compare graphs.

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

• Abstract semantic graph — A graph representation of a formal expression or program whose nodes denote terms or semantic entities and whose shared nodes can represent common subexpressions beyond an abstract syntax tree.
• 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.
• Balanced hypergraph — A hypergraph with no strong odd cycle, equivalently one whose incidence matrix is balanced and supports bipartite-like integrality properties.
• 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.
• 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.
• Cube-connected cycles — A cubic interconnection graph formed by replacing each hypercube vertex with a cycle and distributing cube dimensions around that cycle.
• 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.
• 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.
• 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.
• End (graph theory) — An equivalence class of one-way infinite paths that remain connected in the same unbounded component after deletion of every finite vertex set.
• Euler tour technique — A tree representation that replaces each undirected edge with two directed arcs and linearizes the resulting Euler tour for efficient queries and updates.
• 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.
• Graceful labeling — An injective vertex labeling from zero through the edge count whose absolute edge differences are exactly one through that count.
• 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.
• Hanani–Tutte theorem — A planarity theorem stating that a graph is planar when it has a plane drawing in which every pair of independent edges crosses an even number of times.
• 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.
• 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.
• Queue number — The minimum number of edge queues needed in a vertex ordering of a graph so no two edges in the same queue are properly nested.
• 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.
• Signed graph — A graph whose edges carry positive or negative signs, with cycle-sign products determining balance and switching equivalence.
• 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.
• 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.
• Transitive reduction — A smallest-edge directed graph preserving exactly the reachability relation of a given directed graph.
• Treewidth — The minimum, over all tree decompositions of a graph, of the largest bag size minus one, measuring how closely the graph can be organized around tree-like separators.
• 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.
• Zero-symmetric graph — A connected cubic graph whose automorphism group acts regularly on vertices but is not transitive on edges.