A note on the \(f\)-factor-lattice of bipartite graphs (Q1204470)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the \(f\)-factor-lattice of bipartite graphs |
scientific article |
Statements
A note on the \(f\)-factor-lattice of bipartite graphs (English)
0 references
10 March 1993
0 references
Let \(G\) be a bipartite graph \(G=(X\cup Y,E)\) and \(F\) one of its subgraphs. Let \(f\) be a \((m+n)\)-dimensional vector which coordinates are the degrees of the vertices \(x_ 1,x_ 2,\dots,x_ m\in X\) and \(y_ 1,y_ 2,\dots,y_ n\in Y\) of the subgraph \(F\). Then the subgraph \(F\) is called the \(f\)-factor of \(G\). The author investigated the \(f\)-factor lattice of bipartite graphs. His result is a generalization of the Lovász characterization of the lattice generated by the perfect matchings in bipartite graphs (given in [J. Comb. Theory, Ser. B 43, 187-222 (1987; Zbl 0659.05081)]). The \(f\)-factor lattice is characterized using a generalization of the known Hall marriage condition for bipartite graphs. The author gives also a generalization in matroid theory.
0 references
\(f\)-factor
0 references
bipartite graph
0 references
perfect matchings
0 references
matroid
0 references