Biased Graph - Minors

Minors

A minor of a biased graph Ω = (G, B) is the result of any sequence of taking subgraphs and contracting edge sets. For biased graphs, as for graphs, it suffices to take a subgraph (which may be the whole graph) and then contract an edge set (which may be the empty set).

A subgraph of Ω consists of a subgraph H of the underlying graph G, with balanced circle class consisting of those balanced circles that are in H. The deletion of an edge set S, written Ω − S, is the subgraph with all vertices and all edges except those of S.

Contraction of Ω is relatively complicated. To contract one edge e, the procedure depends on the kind of edge e is. If e is a link, contract it in G. A circle C in the contraction G/e is balanced if either C or is a balanced circle of G. If e is a balanced loop or a loose edge, it is simply deleted. If it is an unbalanced loop or a half-edge, it and its vertex v are deleted; each other edge with v as an endpoint loses that endpoint, so a link with v as one endpoint becomes a half-edge at its other endpoint, while a loop or half-edge at v becomes a loose edge.

In the contraction Ω/S by an arbitrary edge set S, the edge set is E − S. (We let G = (V, E).) The vertex set is the class of vertex sets of balanced components of the subgraph (V, S) of Ω. That is, if (V, S) has balanced components with vertex sets V₁, ..., V_k, then Ω/S has k vertices V₁, ..., V_k . An edge e of Ω, not in S, becomes an edge of Ω/S and each endpoint v_i of e in Ω that belongs to some V_i becomes the endpoint V_i of e in Ω/S ; thus, an endpoint of e that is not in a balanced component of (V, S) disappears. An edge with all endpoints in unbalanced components of (V, S) becomes a loose edge in the contraction. An edge with only one endpoint in a balanced component of (V, S) becomes a half-edge. An edge with two endpoints that belong to different balanced components becomes a link, and an edge with two endpoints that belong to the same balanced component becomes a loop.