Biased graph

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. Formally, a biased graph Ω is a pair (G, B) where B is a linear class of circles; this by definition is a class of circles that satisfies the theta-graph property mentioned above. A subgraph or edge set whose circles are all in B (and which contains no half-edges) is called balanced. For instance, a circle belonging to B is balanced and one that does not belong to B is unbalanced. Biased graphs are interesting mostly because of their matroids, but also because of their connection with multiary quasigroups. See below. 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. 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 2Cn . Such biased graphs in which no digon (circle of length 2) is balanced lead to spikes and swirls (see Matroids, below).