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

2023/02/21 by Lixiang Chen, Edwin van Dam, Chen, Lixiang +3 · 6 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Tensor decomposition and applications

paper · doi:10.48550/arxiv.2302.10496

openalex publication_date 2023/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Spectral characterizations of local structures of graphs and hypergraphs
• Perron-Frobenius theorem for dual tensors and its applications
• The ordering of hypertrees and unicyclic hypergraphs by the traces of A_α-tensor
• The characteristic polynomial of sunflowers
• An α-triangle eigenvector centrality of graphs
• Lexicographical ordering by spectral moments of bicyclic hypergraphs

Related

• Some spectral properties of uniform hypergraphs
• The Laplacian spectral moments of power hypergraphs
• The characteristic polynomials of r-uniform hypercycles with length l
• Walks, infinite series and spectral radius of graphs
• All eigenvalues of the power hypergraph and signed subgraphs of a graph