Z.Fueredi and D.Kleitman proved that if an integer weight is assigned to each edge of a complete graph on p+1 vertices, then there is a spanning tree whose edges have weights summing to zero modulo p. This result has a number of conjectured extensions; and in this paper we prove some of them when p is prime. In particular, we prove that for any graph G and prime p, if integer weights can be assigned to the edges of G so that no spanning tree has weights summing to zero modulo p, then such a weighting can be chosen that is (0,1)-valued. We also prove that, under appropriate hypotheses, there are many spanning trees, all with different total weight modulo p. Matroid extensions of these last results generalize theorems from additive number theory.
展开▼
