JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 4, No 2 (1995)

R. Aharoni , R. Meshulam and B. Wajnryb

Let G be a bipartite graph with bicoloration { A, B}, | A| = | B|, and let w : E( G) w( S) = Õ _{e Ĩ S} w( e) w(S) = \prod {_{e \in S} w(e)} . A Perfect matching M Ĩ \in A, then either G has no w-matchings, or G has at least ( d - 1)! w-matchings.

1. R. Aharoni, R. Manber, and B. Wajnryb, "Special parity of perfect matchings in bipartite graphs," Discrete Math. 79 (1989/1990), 221-228.
2. R. C. Baker and W. M. Schmidt, "Diophantine problems in variables restricted to the values 0 and 1," J. Number Theory 12 (1980), 460-486.
3. P. Van Emde Boas and D. Kruyswijk, "A combinatorial problem on finite abelian groups III," Z.W. 1969-008 (Math. Centrum, Amsterdam).
4. L. Lovasz, Combinatorial problems and exercises, North-Holland, New York, 1979.
5. R. Meshulam, "An uncertainty inequality and zero subsums," Discrete Math. 84 (1990), 197-200.
6. J. E. Olson, "A combinatorial problem on finite abelian groups I," J. Number Theory 1 (1969), 8-10.
7. Y. Rinnot, Private communication, November 1991.
8. C. Thomassen, "Disjoint cycles in digraphs," Combinatorica 3 (1983), 393-396.