New graph invariants based on p-Laplacian eigenvalues

2023/10/12 by Ge, Chuanyuan, Liu, Shiping, Zhang, Dong
#Combinatorics (math.CO) #FOS: Mathematics #Spectral Theory (math.SP)

paper · doi:10.48550/arxiv.2310.08189

Abstract

We present monotonicity inequalities for certain functions involving eigenvalues of p-Laplacians on signed graphs with respect to p. Inspired by such monotonicity, we propose new spectrum-based graph invariants, called (variational) cut-off adjacency eigenvalues, that are relevant to certain eigenvector-dependent nonlinear eigenvalue problem. Using these invariants, we obtain new lower bounds for the p-Laplacian variational eigenvalues, essentially giving the state-of-the-art spectral asymptotics for these eigenvalues. Moreover, based on such invariants, we establish two inertia bounds regarding the cardinalities of a maximum independent set and a minimum edge cover, respectively. The first inertia bound enhances the classical Cvetković bound, and the second one implies that the k-th p-Laplacian variational eigenvalue is of the order 2^p as p tends to infinity whenever k is larger than the cardinality of a minimum edge cover of the underlying graph. We further discover an interesting connection between graph p-Laplacian eigenvalues and tensor eigenvalues and discuss applications of our invariants to spectral problems of tensors.

Related

• Computing the p-Laplacian eigenpairs of signed graphs
• The graph ∞-Laplacian eigenvalue problem
• A nodal domain theorem and a higher-order Cheeger inequality for the\n graph p-Laplacian
• Nodal domain theorems for p-Laplacians on signed graphs
• Eigenvalues of graph Laplacians via rank-one perturbations