On zero-sum spanning trees and zero-sum connectivity

Yair Caro ; Adriana Hansberg ; Josef Lauri ; Christina Zarb

The electronic journal of combinatorics, Tome 29 (2022) no. 1

Résumé

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.

Détail

DOI : 10.37236/10289

Classification : 05C35, 05C05, 05C40
Mots-clés : complete graphs, \(K_3\)-free graphs, \(d\)-trees, maximal planar graphs, zero-sum spanning path, zero-sum spanning tree