Definition
Formally, 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 β assigning an X-flap β(X) to every set X of fewer than k vertices, satisfying 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 the following 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.
Havens with the touching definition are closely related to brambles, families of connected subgraphs of a given graph that all touch each other. The order of a bramble is the minimum number of vertices needed in a set of vertices that hits all of the subgraphs in the family; the set of flaps β(X) for a haven of order k (with the touching definition) forms a bramble of order k. Conversely, given a bramble of order k, one may define a haven of the same order, by defining β(X) to be the X-flap that includes all of the subgraphs in the bramble that are disjoint from X. The requirement that the subgraphs in the bramble all touch each other ensures that this X-flap is unique, and that all chosen flaps touch each other.
Read more about this topic: Haven (graph Theory)
Famous quotes containing the word definition:
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)