Biased graph

Last updated June 18, 2022

In mathematics, a biased graph is a graph with a list of distinguished circles (edge sets of simple cycles), such that if two circles in the list are contained in a theta graph, then the third circle of the theta graph is also in the list. A biased graph is a generalization of the combinatorial essentials of a gain graph and in particular of a signed graph.

Technical notes

A biased graph may have half-edges (one endpoint) and loose edges (no endpoints). The edges with two endpoints are of two kinds: a link has two distinct endpoints, while a loop has two coinciding endpoints.

Linear classes of circles are a special case of linear subclasses of circuits in a matroid.

Examples

If every circle belongs to B, and there are no half-edges, Ω is balanced. A balanced biased graph is (for most purposes) essentially the same as an ordinary graph.
If B is empty, Ω is called contrabalanced. Contrabalanced biased graphs are related to bicircular matroids.
If B consists of the circles of even length, Ω is called antibalanced and is the biased graph obtained from an all-negative signed graph.
The linear class B is additive, that is, closed under repeated symmetric difference (when the result is a circle), if and only if B is the class of positive circles of a signed graph.
Ω may have underlying graph that is a cycle of length n ≥ 3 with all edges doubled. Call this a biased 2C_n . Such biased graphs in which no digon (circle of length 2) is balanced lead to spikes and swirls (see Matroids, below).
Some kinds of biased graph are obtained from gain graphs or are generalizations of special kinds of gain graph. The latter include biased expansion graphs, which generalize group expansion graphs.

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 $C\cup e$ 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.

Matroids

There are two kinds of matroid associated with a biased graph, both of which generalize the cycle matroid of a graph (Zaslavsky, 1991).

The frame matroid

The frame matroid (sometimes called bias matroid) of a biased graph, M(Ω), (Zaslavsky, 1989) has for its ground set the edge set E. An edge set is independent if each component contains either no circles or just one circle, which is unbalanced. (In matroid theory a half-edge acts like an unbalanced loop and a loose edge acts like a balanced loop.) M(Ω) is a frame matroid in the abstract sense, meaning that it is a submatroid of a matroid in which, for at least one basis, the set of lines generated by pairs of basis elements covers the whole matroid. Conversely, every abstract frame matroid is the frame matroid of some biased graph.

The circuits of the matroid are called frame circuits or bias circuits. There are four kinds. One is a balanced circle. Two other kinds are a pair of unbalanced circles together with a connecting simple path, such that the two circles are either disjoint (then the connecting path has one end in common with each circle and is otherwise disjoint from both) or share just a single common vertex (in this case the connecting path is that single vertex). The fourth kind of circuit is a theta graph in which every circle is unbalanced.

The rank of an edge set S is n−b, where n is the number of vertices of G and b is the number of balanced components of S, counting isolated vertices as balanced components.

Minors of the frame matroid agree with minors of the biased graph; that is, M(Ω−S) = M(Ω)−S and M(Ω/S) = M(Ω)/S.

Frame matroids generalize the Dowling geometries associated with a group (Dowling, 1973). The frame matroid of a biased 2C_n (see Examples, above) which has no balanced digons is called a swirl. It is important in matroid structure theory.

The lift matroid

The extended lift matroidL₀(Ω) has for its ground set the set E₀, which is the union of E with an extra pointe₀. The lift matroidL(Ω) is the extended lift matroid restricted to E. The extra point acts exactly like an unbalanced loop or a half-edge, so we describe only the lift matroid.

An edge set is independent if it contains either no circles or just one circle, which is unbalanced.

A circuit is a balanced circle, a pair of unbalanced circles that are either disjoint or have just a common vertex, or a theta graph whose circles are all unbalanced.

The rank of an edge set S is n−c + ε, where c is the number of components of S, counting isolated vertices, and ε is 0 if S is balanced and 1 if it is not.

Minors of the lift and extended lift matroids agree in part with minors of the biased graph. Deletions agree: L(Ω−S) = L(Ω)−S. Contractions agree only for balanced edge sets: M(Ω/S) = M(Ω)/S if S is balanced, but not if it is unbalanced. If S is unbalanced, M(Ω/S) = M(G)/S = M(G/S) where M of a graph denotes the ordinary graphic matroid.

The lift matroid of a 2C_n (see Examples, above) which has no balanced digons is called a spike. Spikes are quite important in matroid structure theory.

Multiary quasigroups

Just as a group expansion of a complete graph K_n encodes the group (see Dowling geometry), its combinatorial analog expanding a simple cycle of length n + 1 encodes an n-ary (multiary) quasigroup. It is possible to prove theorems about multiary quasigroups by means of biased graphs (Zaslavsky, t.a.)

Related Research Articles

Bipartite graph Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

Signed graph Graph with sign-labeled edges

In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.

In the mathematical discipline of graph theory, the dual graph of a plane graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

Wagners theorem Characterization theorem in graph theory of planar graphs

In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K₅ nor K_3,3. This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.

In combinatorial mathematics, a Dowling geometry, named after Thomas A. Dowling, is a matroid associated with a group. There is a Dowling geometry of each rank for each group. If the rank is at least 3, the Dowling geometry uniquely determines the group. Dowling geometries have a role in matroid theory as universal objects ; in that respect they are analogous to projective geometries, but based on groups instead of fields.

A gain graph is a graph whose edges are labelled "invertibly", or "orientably", by elements of a group G. This means that, if an edge e in one direction has label g, then in the other direction it has label g⁻¹. The label function φ therefore has the property that it is defined differently, but not independently, on the two different orientations, or directions, of an edge e. The group G is called the gain group, φ is the gain function, and the value φ(e) is the gain of e. A gain graph is a generalization of a signed graph, where the gain group G has only two elements. See Zaslavsky.

In graph theory, a mathematical discipline, a factor-critical graph is a graph with $n$ vertices in which every subgraph of $n - 1$ vertices has a perfect matching.

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.

Pseudoforest Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In the mathematical subject of matroid theory, the bicircular matroid of a graph G is the matroid B(G) whose points are the edges of G and whose independent sets are the edge sets of pseudoforests of G, that is, the edge sets in which each connected component contains at most one cycle.

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.

In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn − k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.

References

T. A. Dowling (1973), A class of geometric lattices based on finite groups. Journal of Combinatorial Theory, Series B, Vol. 14, pp. 61–86.
Thomas Zaslavsky (1989), Biased graphs. I. Bias, balance, and gains. Journal of Combinatorial Theory, Series B, Vol. 47, pp. 32–52.
Thomas Zaslavsky (1991), Biased graphs. II. The three matroids. Journal of Combinatorial Theory, Series B, Vol. 51, pp. 46–72.
Thomas Zaslavsky (1999). A mathematical bibliography of signed and gain graphs and allied areas. 1999 edition: Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, #DS8, archived. Current edition: Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, #DS8.
Thomas Zaslavsky (2012), Associativity in multiary quasigroups: the way of biased expansions. Aequationes Mathematicae , Vol. 83, pp. 1–66.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.