On zero-sum spanning trees and zero-sum connectivity (Q2073300)

Summary: We consider 2-colourings \(f : E(G) \rightarrow \{ -1 ,1 \}\) of the edges of a graph \(G\) with colours \(-1\) and \(1\) in \(\mathbb{Z} \). A subgraph \(H\) of \(G\) is said to be a zero-sum subgraph of \(G\) under \(f\) if \(f(H) := \sum_{e\in 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, \(K_3\)-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 = K_n\), a sharp bound on \(|f(K_n)|\) 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.