Spectra of power hypergraphs and signed graphs via parity-closed walks

The k-power hypergraph G(k) is the k-uniform hypergraph that is obtained by adding k−2 new vertices to each edge of a graph G, for k≥3. A parity-closed walk in G is a closed walk that uses each edge an even number of times. In an earlier paper, we determined the eigenvalues of the adjacency tensor of G(k) using the eigenvalues of signed subgraphs of G. Here, we express the entire spectrum (that is, we determine all multiplicities and the characteristic polynomial) of G(k) in terms of parity-closed walks of G. Moreover, we give an explicit expression for the multiplicity of the spectral radius of G(k). Our results are mainly obtained by exploiting the so-called trace formula to determine the spectral moments of G(k). As a side result, we show that the number of parity-closed walks of given length is the corresponding spectral moment averaged over all signed graphs with underlying graph G. We also extrapolate the characteristic polynomial of G(k) to k=2, thereby introducing a pseudo-characteristic function. Among other results, we show that this function is the geometric mean of the characteristic polynomials of all signed graphs on G and characterize when it is a polynomial. This supplements a result by Godsil and Gutman that the arithmetic mean of the characteristic polynomials of all signed graphs on G equals the matching polynomial of G.