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 }$-analogue by Andrade and Dahl, we investigate the graph parameter ${\hat{I}}^3(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 ${\hat{I}}^3(G)$ as the ratio of the order of the graph to its maximum transmission, thereby providing a direct graph-theoretic interpretation of the parameter. As a consequence, we obtain a polynomial-time algorithm based on breadth-first search, significantly simplifying the previously known linear programming approach. We prove that ${\hat{I}}^3(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. Furthermore, we derive bounds for ${\hat{I}}^3(G)$ in terms of several classical graph invariants, including the distance spectral radius, Wiener index, algebraic connectivity, and Cheeger constant. Finally, we establish a product formula for ${\hat{I}}^3(G)$ under Cartesian products of graphs, leading to explicit expressions for important graph families such as hypercubes, Hamming graphs, grid graphs, and torus graphs.