The neighbour-sum problem on graphs
For which graphs does there exist a non-trivial solution?
R.E.J. Cuypers (TU Delft - Electrical Engineering, Mathematics and Computer Science)
D.C. Gijswijt – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
E. Lorist – Graduation committee member (TU Delft - Electrical Engineering, Mathematics and Computer Science)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The neighbour-sum problem asks whether a graph admits a non-trivial assignment of real numbers to its vertices such that the value at each vertex equals the sum of the values assigned to its neighbours. This problem can be reformulated as the eigenvalue equation Ax=x, where A is the adjacency matrix of the graph, reducing the question to determining whether 1 is an eigenvalue of A.
This thesis investigates the neighbour-sum problem for several classes of graphs using techniques from spectral graph theory, linear algebra, and Fourier analysis on finite groups. Complete characterizations are obtained for path graphs and cycle graphs through explicit formulas for their spectra. These results are extended to Cayley graphs over finite abelian groups, yielding explicit eigenvalue conditions for circulant graphs in terms of group characters. For trees, theoretical results are derived for several special families, including stars, double stars, and caterpillar trees, and an asymptotic result shows that the proportion of solvable trees tends to one as the number of vertices increases.
In addition, computational experiments were performed on all non-isomorphic trees with up to twenty vertices and on connected circulant graphs of small order. The experiments reveal how structural properties such as the number of leaves, maximum degree, diameter, and generating set influence solvability, and suggest that larger trees are increasingly likely to admit non-trivial solutions. Together, the theoretical and computational results provide insight into the relationship between graph structure and the existence of neighbour-sum assignments.