The Graph ∞-Laplacian Eigenvalue Problem

We analyze various formulations of the infinity-Laplacian eigenvalue problem on graphs, comparing their properties and highlighting their respective advantages and limitations. First, we investigate the graph infinity-eigenpairs arising as limits of p-Laplacian eigenpairs, extending key results from the continuous setting to the discrete domain. We prove that every limit of p-Laplacian eigenpair, for p going to infinity, satisfies a limit eigenvalue equation and establishes that the corresponding eigenvalue can be bounded from below by the packing radius of the graph, indexed by the number of nodal domains induced by the eigenfunction. Additionally, we show that the limits, for p going to infinity, of the variational p-Laplacian eigenvalues are bounded from both above and below by the packing radii, achieving equality for the smallest two variational eigenvalues and corresponding packing radii of the graph. In the second part of the paper, we introduce generalized infinity-Laplacian eigenpairs as generalized critical points and values of the infinity-Rayleigh quotient. We prove that the generalized variational infinity-eigenvalues equal the limit of the p-Laplacian variational eigenvalues and so satisfy the same upper bounds in terms of packing radii. Finally, we establish that any solution to the limit eigenvalue equation is also a generalized eigenpair, while any generalized eigenpair satisfies the limit eigenvalue equation on a suitable subgraph.