Zero-Sum Copies of Spanning Forests in Zero-Sum Complete Graphs

Abstract

For a complete graph $K_n$ of order n, an edge-labeling $c:E(K_n)\rightarrow \{ -1,1\}$ satisfying $c(E(K_n))=0$, and a spanning forest F of $K_n$, we consider the problem to minimize $|c(E(F'))|$ over all isomorphic copies $F'$ of F in $K_n$. In particular, we ask under which additional conditions there is a zero-sum copy, that is, a copy $F'$ of F with $c(E(F'))=0$. We show that there is always a copy $F'$ of F with $|c(E(F'))|\le \Delta (F)+1$, where $\Delta (F)$ is the maximum degree of F. We conjecture that this bound can be improved to $|c(E(F'))|\le (\Delta (F)-1)/2$ and verify this for F being the star $K_{1,n-1}$. Under some simple necessary divisibility conditions, we show the existence of a zero-sum $P_3$-factor, and, for sufficiently large n, also of a zero-sum $P_4$-factor.