Group weighted matchings in bipartite graphs (Q1804248): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1023/a:1022433630971 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W51758890 / rank | |||
Normal rank |
Latest revision as of 11:41, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Group weighted matchings in bipartite graphs |
scientific article |
Statements
Group weighted matchings in bipartite graphs (English)
0 references
25 September 1997
0 references
Let \(G\) be a bipartite graph with equal number of vertices of both colours, and \(K\) a (multiplicative) finite abelian group. Let \(M\) denote all mappings \(w:E(G) \rightarrow K\), which have \(w(M)=1\) for each perfect matching of \(G\). (The value \(w(M)\) is the product of all \(w(e), e\in M\).) Finally, \(U\) is the subset of all \(w \in M\) obtained by choosing a function \(\alpha\) on the black vertices of \(G\) and another function \(\beta\) on the white vertices of \(G\), both with values in \(K\), so that the product of all \(\alpha(v)\) and \(\beta(v)\) is \(1\), and letting \(w(a,b)=\alpha(a)\beta(b)\). If \(K\) is the trivial group then it is clear that \(M=U\). The authors prove that if each edge of \(G\) lies in a perfect matching then \(M=U\). (This has been proved earlier for the special case of the two-element group \(K\).) They also prove that if \(G\) is a complete bipartite graph with \(k+1\) vertices of each colour, and \(K\) has \(k\) elements, then for any \(w \in F\), the existence of one perfect matching \(M\) with \(w(M)=1\) implies the existence of at least one other such perfect matching. Finally, the authors consider again the two-element group \(K\), and prove, for any \(w \in F\), if \(G\) has all degrees of white vertices at least \(d\), the existence of one perfect matching \(M\) with \(w(M)=1\) implies the existence of at least \((d-1)!\) such perfect matchings. The last two results are modified for digraphs, and applied to solve a problem of Rinnot on random matrices.
0 references
bipartite matching
0 references
abelian group
0 references
edge labels
0 references