A combinatorial development of Fibonacci numbers in graph spectra

Consider a graph whose vertices are the distinguishable submultisets of a finite multiset such that two vertices r and s are adjacent if and only if r∩s=∅. In this paper, the walks on these graphs are linked to square and domino-tilings of rectangular and circular boards. Among the results provided, the number of walks of any given length is shown to be a product of generalized Fibonacci numbers. As an application, the eigenvalues are computed for the (unrestricted) zero-divisor graphs of finite commutative rings without nonzero nilpotents.