View PDF HTML (experimental)

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 $\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. 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 $\gamma(G)$ characterizes graph connectivity and completely characterize all $\ell_\infty$-Fiedler vectors as the vectors
\[
\left\{\pm\left(1-\gamma(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 $\gamma(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 $\gamma(G)$ under Cartesian products of graphs, leading to explicit expressions for important graph families such as hypercubes, Hamming graphs, grid graphs, and torus graphs.

Submission history

From: M Rajesh Kannan [view email]
[v1] Tue, 29 Jul 2025 17:06:09 UTC (17 KB)
[v2] Mon, 3 Aug 2026 07:28:47 UTC (14 KB)