Matchings and spanning trees in Boolean weighted graphs |
| |
Authors: | Kenneth A Berman |
| |
Institution: | University of Waterloo, Waterloo, Ontario, Canada |
| |
Abstract: | It is shown that in a 0-sum Boolean weighted graph G the sum of the weights taken over all the spanning trees equals the sum of the weights taken over all the perfect matchings in the graph G − v, where v is any vertex of G. Several related theorems are proved which include parity results on perfect matchings and spanning trees in Eulerian graphs. The ideas on perfect matchings in 0-sum Boolean weighted graphs are generalized to matchings in any Boolean weighted graph. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|