Haven (graph Theory) - in Infinite Graphs

In Infinite Graphs

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 ℵ₀: that is, a function β that maps each finite set X of vertices to an X-flap, satisfying the consistency condition for havens. Namely, define β(X) to be the unique X-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. If the haven has the property that the intersection ( where the intersection ranges over all finite sets X) is itself an infinite set S, then there exists a ray passing through infinitely many vertices of S, and this ray determines the haven. On the other hand, if S is finite, then (by working in the subgraph G \ S) it can be assumed to be empty. In this case, for each finite set X_i of vertices there is a set X_{i + 1} with the property that X_i is disjoint from . If a robber follows the evasion strategy defined by the haven for this sequence of sets, 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, an infinite graph G has a haven of order κ if and only if it has a clique minor of order κ. That is, the largest order of a haven in G is the Hadwiger number of G.