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)\to \{-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^{\prime }))|$ over all isomorphic copies $F^{\prime }$ of $F$ in $K_n$. In particular, we ask under which additional conditions there is a zero-sum copy, that is, a copy $F^{\prime }$ of $F$ with $c(E(F^{\prime }))=0$. We show that there is always a copy $F^{\prime }$ of $F$ with $|c(E(F^{\prime }))|\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^{\prime }))|\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.