The Neighbour Sum Problem on Trees

Abstract

A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is said to satisfy the Neighbour Sum Property if there exists some $f:\mathcal{V}\to \mathbb{R}$ such that $f\not\equiv 0$ and it maps every vertex to the sum of the values taken by its neighbours. In this article, we provide an algorithm to check whether a given finite tree satisfies the neighbour sum property. We also find a large class of trees on $n$ vertices that satisfy the property.