Haven (graph theory)

Havens were first introduced by Seymour & Thomas (1993) as a tool for characterizing the treewidth of graphs.

[3][4] 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.

[5] In the original definition of Seymour and Thomas,[1] 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.

The set of flaps β(X) for a haven of order k (with the touching definition) forms a bramble of order at least k, because any set Y of fewer than k vertices fails to hit the subgraph β(Y).

Define a haven of order 4 in G, mapping each set X of three or fewer vertices to an X-flap β(X), as follows: It is straightforward to verify by a case analysis that this function β satisfies the required monotonicity property of a haven.

However, before a new pursuer is added, the evader is first informed of its new location and may move along the edges of the graph to any unoccupied vertex.

If a k-haven (with the monotonicity property) exists, then the evader may avoid being captured indefinitely, and win the game, by always moving to a vertex of β(X) where X is the set of vertices that will be occupied by pursuers at the end of the move.

The monotonicity property of a haven guarantees that, when a new pursuer is added to a vertex of the graph, the vertices in β(X) are always reachable from the current position of the evader.

[1] For instance, an evader can win this game against three pursuers on a 3 × 3 grid by following this strategy with the haven of order 4 described in the example.

Havens with the touching property allow the evader to win the game against more powerful pursuers that may simultaneously jump from one set of occupied vertices to another.

In games won by the evader, there is always an optimal strategy in the form described by a haven, and in games won by the pursuer, there is always an optimal strategy in the form described by a tree decomposition.

In this case, G has a haven of order k + 1, in which β(X) is defined to be this unique large X-flap.

In other words, the Hadwiger number of an n-vertex graph with a haven of order k is at least k2/3n-1/3.

[2] If a graph G contains a ray, a semi-infinite simple path with a starting vertex but no ending vertex, then it has a haven of order ℵ0: that is, a function β that maps each finite set X of vertices to an X-flap, satisfying the consistency condition for havens.