On zero-sum spanning trees and zero-sum connectivity

Abstract

We consider 2-colourings f : E(G) → {−1, 1} of the edges of a graph G with colours −1 and 1 in Z. A subgraph H of G is said to be a zero-sum subgraph of G under f if f(H) := P e∈E(H) f(e) = 0. We study the following type of questions, in several cases obtaining best possible results: Under which conditions on |f(G)| can we guarantee the existence of a zero-sum spanning tree of G? The types of G we consider are complete graphs, K3-free graphs, d-trees, and maximal planar graphs. We also answer the question of when any such colouring contains a zero-sum spanning path or a zero-sum spanning tree of diameter at most 3, showing in passing that the diameter-3 condition is best possible. Finally, we give, for G = Kn, a sharp bound on |f(Kn)| by which an interesting zero-sum connectivity property is forced, namely that any two vertices are joined by a zero-sum path of length at most 4. One feature of this paper is the proof of an Interpolation Lemma leading to a Master Theorem from which many of the above results follow and which can be of independent interest.