Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose
that on each vertex of the graph there is a player having an $n$-bit
string. Each player is allowed to communicate with its neighbors according
to an agreed communication protocol, and the players must decide,
deterministically, if their inputs are all equal. What is the minimum
possible total number of bits transmitted in a protocol solving
this problem ? We determine this minimum up to a lower order
additive term in many cases (but not for all graphs).
In particular, we show that it is $kn/2+o(n)$ for any
Hamiltonian $k$-vertex graph, and that for any $2$-edge connected
graph with $m$ edges containing no
two adjacent vertices of degree exceeding $2$ it is $mn/2+o(n)$.
The proofs combine graph theoretic ideas with
tools from additive number theory.

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose
that on each vertex of the graph there is a player having an $n$-bit
string. Each player is allowed to communicate with its neighbors according
to an agreed communication protocol, and the players must decide,
deterministically, if their inputs are all equal. What is the minimum
possible total number of bits transmitted in a protocol solving
this problem ? We determine this minimum up to a lower order
additive term in many cases (but not for all graphs).
In particular, we show that it is $kn/2+o(n)$ for any
Hamiltonian $k$-vertex graph, and that for any $2$-edge connected
graph with $m$ edges containing no
two adjacent vertices of degree exceeding $2$ it is $mn/2+o(n)$.
The proofs combine graph theoretic ideas with
tools from additive number theory.