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.
The bicircular matroid was introduced by Simões-Pereira (1972) and explored further by Matthews (1977) and others. It is a special case of the frame matroid of a biased graph.
The circuits, or minimal dependent sets, of this matroid are the bicircular graphs (or bicycles, but that term has other meanings in graph theory); these are connected graphs whose circuit rank is exactly two.
There are three distinct types of bicircular graph:
All these definitions apply to multigraphs, i.e., they permit multiple edges (edges sharing the same endpoints) and loops (edges whose two endpoints are the same vertex).
The closed sets (flats) of the bicircular matroid of a graph G can be described as the forests F of G such that in the induced subgraph of V(G) −V(F), every connected component has a cycle. Since the flats of a matroid form a geometric lattice when partially ordered by set inclusion, these forests of G also form a geometric lattice. In the partial ordering for this lattice, that F1≤F2 if
For the most interesting example, let G o be G with a loop added to every vertex. Then the flats of B(G o) are all the forests of G, spanning or nonspanning. Thus, all forests of a graph G form a geometric lattice, the forest lattice of G( Zaslavsky 1982 ).
Bicircular matroids can be characterized as the transversal matroids that arise from a family of sets in which each set element belongs to at most two sets. That is, the independent sets of the matroid are the subsets of elements that can be used to form a system of distinct representatives for some or all of the sets. In this description, the elements correspond to the edges of a graph, and there is one set per vertex, the set of edges having that vertex as an endpoint.
Unlike transversal matroids in general, bicircular matroids form a minor-closed class; that is, any submatroid or contraction of a bicircular matroid is also a bicircular matroid, as can be seen from their description in terms of biased graphs ( Zaslavsky 1991 ). Here is a description of deletion and contraction of an edge in terms of the underlying graph: To delete an edge from the matroid, remove it from the graph. The rule for contraction depends on what kind of edge it is. To contract a link (a non-loop) in the matroid, contract it in the graph in the usual way. To contract a loop e at vertex v, delete e and v but not the other edges incident with v; rather, each edge incident with v and another vertex w becomes a loop at w. Any other graph loops at v become matroid loops—to describe this correctly in terms of the graph one needs half-edges and loose edges; see biased graph minors.
The characteristic polynomial of the bicircular matroid B(G o) expresses in a simple way the numbers of spanning forests (forests that contain all vertices of G) of each size in G. The formula is
where fk equals the number of k-edge spanning forests in G. See Zaslavsky (1982).
Bicircular matroids, like all other transversal matroids, can be represented by vectors over any infinite field. However, unlike graphic matroids, they are not regular: they cannot be represented by vectors over an arbitrary finite field. The question of the fields over which a bicircular matroid has a vector representation leads to the largely unsolved problem of finding the fields over which a graph has multiplicative gains. See Zaslavsky (2007).
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.
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.
In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.
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, two graphs and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if their diagrams are homeomorphic in the topological sense.
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, 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.
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 mathematics, a biased graph is a graph with a list of distinguished circles, 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.
In the mathematical discipline of graph theory, the dual graph of a planar 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.
In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.
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 (a group element), then in the other direction it has label g −1. 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 (in some indicated direction). A gain graph is a generalization of a signed graph, where the gain group G has only two elements. See Zaslavsky (1989, 1991).
In graph theory, a mathematical discipline, a factor-critical graph is a graph with n vertices in which every induced subgraph of n − 1 vertices has a perfect matching.
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 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, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other.
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.
