rootminor

Rootminor, or rooted minor, is a concept in graph theory describing a minor of a graph that preserves a prescribed set of vertices called roots or terminals. It formalizes contracting parts of a graph while keeping track of where certain distinguished vertices lie within the minor. Rooted minors are used to study how terminals interact under graph contractions and deletions, and they appear in various algorithmic and structural aspects of the graph minor theory developed by Robertson and Seymour.

Definition: Let G be a graph and R ⊆ V(G) a set of roots. A rooted minor of (G, R) is a pair (H, μ) where H is a graph and μ is an injective function from R into V(H) such that there exists a collection {B_v : v ∈ V(H)} of nonempty, connected, pairwise vertex-disjoint subgraphs of G (the branch sets) with r ∈ B_{μ(r)} for all r ∈ R. For every edge uv ∈ E(H), the corresponding branch sets B_u and B_v are joined by at least one edge in G (equivalently, contracting each B_v to a single vertex yields a graph that contains H with the vertex μ(r) corresponding to r). In other words, G contains a minor isomorphic to H in which each root r lies in the branch set associated with μ(r).

Special cases and relation to ordinary minors: If R is empty, a rooted minor reduces to a standard graph minor. If R has a single vertex, one speaks of a rooted minor with respect to that root; more generally, rooted minors add a terminals structure to minors, which is useful for preserving connectivity between specified vertices during contractions.

Applications: Rooted minors appear in structural graph theory, including results about grid minors with terminals and in algorithmic contexts such as Steiner-type problems, fixed-parameter tractable algorithms, and network design where terminals must be preserved under contractions.

See also: graph minor, rooted tree, terminal graph, Steiner tree problem.