Graph Connectivity & Network Measures

← Back to Domain-Specific Families

Abstractions about connectivity, centrality, products, components, regularity, and optimization in graphs and networks. They include structural graph classes, random graphs, factorization, augmentation, width and diameter measures, and computational methods for network organization.

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

• Adjacency list — A graph representation that associates each vertex with a collection of its neighboring vertices or incident edges.
• Betweenness centrality — A network centrality measure equal to the fraction or count of shortest paths between other vertices that pass through a given vertex or edge.
• 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.
• Cavity method — A statistical-physics technique for disordered mean-field systems that removes one variable, characterizes the effective field from the remainder and imposes self-consistency when the variable is restored.
• Claw-free graph — A graph containing no induced subgraph isomorphic to the four-vertex star K1,3.
• 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.
• Cube-connected cycles — A cubic interconnection graph formed by replacing each hypercube vertex with a cycle and distributing cube dimensions around that cycle.
• 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.
• Diameter (graph theory) — Measure a connected graph by the maximum shortest-path distance over all pairs of vertices.
• Domatic number — Assign a graph the largest number of blocks in a vertex partition for which every block is a dominating set.
• 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.
• 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.
• Five-room puzzle — A wall-crossing drawing puzzle whose plan becomes a multigraph and is solvable exactly when the corresponding graph has an Euler trail under the crossing rules.
• 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.
• Held–Karp algorithm — An exact dynamic-programming algorithm for the traveling-salesman problem that stores the cheapest start-to-end path through each subset of cities, reducing tour enumeration to exponential subset recurrence.
• Highly irregular graph — A graph in which the neighbors of every vertex all have pairwise distinct degrees.
• Kronecker graph — A recursively generated graph whose adjacency matrix is formed by repeated Kronecker products of a small initiator matrix, producing large self-similar network structure from few parameters.
• 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.
• 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 — A graph-valued random object specified by a probability distribution or stochastic generation rule over vertices and edges.
• 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.
• 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.
• Strong connectivity augmentation — Add the fewest or least-cost directed edges to a digraph so every vertex can reach every other, with the unweighted optimum governed by source and sink components of the condensation DAG.
• 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).