Extremal Graph Theory & Bounds

← Back to Domain-Specific Families

Abstractions about optimizing graph parameters under structural constraints, covering extremal size problems (cage, the degree diameter problem, the Erdős-Ko-Rado theorem), and structural graph measures (clique, pathwidth).

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

• Cage (Graph Theory) — An r-regular graph of girth g having the minimum possible number of vertices among all graphs with that degree and girth.
• Clique (Graph Theory) — A vertex subset of an undirected graph in which every two distinct vertices are adjacent, equivalently an induced complete subgraph.
• Degree diameter problem — Maximize the number of vertices in a finite graph subject to simultaneous maximum-degree and diameter bounds, comparing constructions with the breadth-first Moore upper bound.
• Erdős–Ko–Rado Theorem — For n at least 2k, a pairwise-intersecting family of k-subsets of an n-element set has at most C(n-1,k-1) members, attained by every full star.
• Pathwidth — Measure how narrowly a graph can be arranged along a path by minimizing the largest bag size minus one over path decompositions with vertex continuity and edge coverage.