Immersion Minor
A graph operation called lifting is central in a concept called immersions. The lifting is an operation on adjacent edges. Given three vertices v, u, and w, where (v,u) and (u,w) are edges in the graph, the lifting of vuw, or equivalent of (v,u), (u,w) is the operation that deletes the two edges (v,u) and (u,w) and adds the edge (v,w). In the case where (v,w) already was present, v and w will now be connected by more than one edge, and hence this operation is intrinsically a multi-graph operation.
In the case where a graph H can be obtained from a graph G by a sequence of lifting operations (on G) and then finding an isomorphic subgraph, we say that H is an immersion minor of G.
The immersion minor relation is a well-quasi-ordering on the set of finite graphs and hence the result of Robertson and Seymour applies to immersion minors. This furthermore means that every immersion minor-closed family is characterized by a finite family of forbidden immersion minors.
Read more about this topic: Graph Minor
Famous quotes containing the word minor:
“If, for instance, they have heard something from the postman, they attribute it to “a semi-official statement”; if they have fallen into conversation with a stranger at a bar, they can conscientiously describe him as “a source that has hitherto proved unimpeachable.” It is only when the journalist is reporting a whim of his own, and one to which he attaches minor importance, that he defines it as the opinion of “well-informed circles.””
—Evelyn Waugh (1903–1966)