On the $l_{\infty }$-analog of Algebraic Connectivity

Abstract

The algebraic connectivity of a graph, defined as the second smallest eigenvalue of its Laplacian matrix, admits a well-known variational characterization involving the ${\ell }_2$-norm. Motivated by the recent introduction of its ${\ell }_{\infty }$-analog by Andrade and Dahl, we investigate the graph parameter $\gamma (G)$, obtained by replacing the ${\ell }_2$-norm with the ${\ell }_{\infty }$-norm in the corresponding optimization problem. We establish a simple and explicit combinatorial formula expressing $\gamma (G)$ as the ratio of the order of the graph to its maximum transmission, thereby providing a direct graph-theoretic interpretation of the parameter. We prove that $\gamma (G)$ characterizes graph connectivity and completely characterize all ${\ell }_{\infty }$-Fiedler vectors as the vectors \[ \left\{\pm\left(1-γ(G)d(u,\cdot)\right):u\in \mathcal{M}(G) \right\}, \] where $\mathcal{M}(G)$ denotes the set of vertices of maximum transmission. We also establish a product formula for $\gamma (G)$ under Cartesian products, yielding explicit expressions for hypercubes, Hamming graphs, and torus grid graphs. Furthermore, we establish comparisons involving $\gamma (G)$, the distance spectral radius, the ${\ell }_1$-smoothing parameter, and the algebraic connectivity, and investigate equality in these bounds. For connected non-complete strongly regular graphs, equality in our algebraic-connectivity bound holds precisely when the least adjacency eigenvalue is $-2$. Finally, we extend the transmission formula and the characterization of optimal vectors to weighted graphs.