On the Hamming Spectrum and Hamming Energy of Graphs

Abstract

In this paper, we study the spectrum of the Hamming matrix H(G) of a simple graph G. The Hamming matrix, recently introduced in terms of the Hamming distances between binary strings derived from the incidence matrix, offers an alternative and insightful perspective on spectral and chemical graph theory. We derive upper and lower bounds for the largest and smallest eigenvalues of the Hamming matrix of paths, respectively, as well as closed-form expressions for the Hamming spectrum and Hamming energy of regular graphs (including cycles as a special case), their complements, and their line graphs, with respect to the classical adjacency spectrum. Furthermore, we provide a factorization that relates the characteristic polynomial of the Hamming matrix of a regular graph to that of its complement and its line graph. These results shed new light on how Hamming-based invariants interact with classical spectral quantities.