Haven (graph theory)

In graph theory, a haven is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit-evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by Seymour & Thomas (1993) as a tool for characterizing the treewidth of graphs. Their other applications include proving the existence of small separators on minor-closed families of graphs, and characterizing the ends and clique minors of infinite graphs.

If G is an undirected graph, and X is a set of vertices, then an X-flap is a nonempty connected component of the subgraph of G formed by deleting X. A haven of order k in G is a function β that assigns an X-flap β(X) to every set X of fewer than k vertices. This function must also satisfy additional constraints which are given differently by different authors. The number k is called the order of the haven.

In the original definition of Seymour and Thomas, a haven is required to satisfy the property that every two flaps β(X) and β(Y) must touch each other: either they share a common vertex or there exists an edge with one endpoint in each flap. In the definition used later by Alon, Seymour, and Thomas, havens are instead required to satisfy a weaker monotonicity property: if X ⊆ Y, and both X and Y have fewer than k vertices, then β(Y) ⊆ β(X). The touching property implies the monotonicity property, but not necessarily vice versa. However, it follows from the results of Seymour and Thomas that, in finite graphs, if a haven with the monotonicity property exists, then one with the same order and the touching property also exists.

...
Wikipedia