Haven (graph theory)
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 as a tool for characterizing the treewidth of graphs.
Definition If is an undirected graph, and is a set of vertices, then an -flap is a nonempty connected component of the subgraph of formed by deleting . A haven of order in is a function that assigns an -flap to every set of fewer than vertices. This function must also satisfy additional constraints which are given differently by different authors. The number 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 and 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,
If a graph has a haven of order , with for some integer , then must also have a complete graph as a minor. In other words, the Hadwiger number of an -vertex graph with a haven of order is at least . As a consequence, the -minor-free graphs have treewidth less than and separators of size less than . More generally an {{tmath|O(\sqrt{n})}} bound on treewidth and separator size holds for any nontrivial family of graphs that can be characterized by forbidden minors, because for any such family there is a constant such that the family does not include .
In infinite graphs If a graph contains a ray, a semi-infinite simple path with a starting vertex but no ending vertex, then it has a haven of order : that is, a function that maps each finite set of vertices to an -flap, satisfying the consistency condition for havens. Namely, define to be the unique -flap that contains infinitely many vertices of the ray. Thus, in the case of infinite graphs the connection between treewidth and havens breaks down: a single ray, despite itself being a tree, has havens of all finite orders and even more strongly a haven of order . Two rays of an infinite graph are considered to be equivalent if there is no finite set of vertices that separates infinitely many vertices of one ray from infinitely many vertices of the other ray; this is an equivalence relation, and its equivalence classes are called ends of the graph.
The ends of any graph are in one-to-one correspondence with its havens of order . For, every ray determines a haven, and every two equivalent rays determine the same haven. Conversely, every haven is determined by a ray in this way, as can be shown by the following case analysis: If the haven has the property that the intersection <p><math>S=\bigcap_X\left(\beta(X)\cup X\right)</math></p><p> (where the intersection ranges over all finite sets ) is itself an infinite set , then every finite simple path that ends in a vertex of can be extended to reach an additional vertex of , and repeating this extension process produces a ray passing through infinitely many vertices of . This ray determines the given haven.</p> On the other hand, if is finite, then (by working in the subgraph )it can be assumed to be empty. In this case, for each finite set of vertices there is a finite set with the property that is disjoint from <math>X_{i+1}\cup\beta(X_{i+1})</math>. If a robber follows the evasion strategy determined by the haven, and the police follow a strategy given by this sequence of sets, then the path followed by the robber forms a ray that determines the haven. Thus, every equivalence class of rays defines a unique haven, and every haven is defined by an equivalence class of rays.
For any cardinal number <math>\kappa\ge\aleph_1</math>, an infinite graph has a haven of order if and only if it has a clique minor of order . That is, for uncountable cardinalities, the largest order of a haven in is the Hadwiger number of .