### Abstract

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 a (static) 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. 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.

Original language | English (US) |
---|---|

Article number | 8016410 |

Pages (from-to) | 7569-7574 |

Number of pages | 6 |

Journal | IEEE Transactions on Information Theory |

Volume | 63 |

Issue number | 11 |

DOIs | |

State | Published - Nov 2017 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Information Systems
- Computer Science Applications
- Library and Information Sciences

### Keywords

- 2-connected graphs
- Communication complexity
- equality function
- static protocols

## Fingerprint Dive into the research topics of 'Testing Equality in Communication Graphs'. Together they form a unique fingerprint.

## Cite this

*IEEE Transactions on Information Theory*,

*63*(11), 7569-7574. [8016410]. https://doi.org/10.1109/TIT.2017.2744608