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

The algebraic connectivity $a(G)$ of a graph $G$ is defined as the second smallest eigenvalue of its Laplacian matrix $L(G)$. It also admits a variational characterization as the minimum of a quadratic form associated with $L(G)$, subject to $l_2$-norm constraints. In 2024, Andrade and Dahl investigated an analogous parameter $\gamma (G)$, defined using the $l_{\mathrm{\infty }}$-norm instead of the $l_2$-norm. They demonstrated that $\gamma (G)$ can be computed in polynomial time using linear programming. In this article, we study the combinatorial significance of $\gamma (G)$, revealing that it can be efficiently computed using a breadth-first search (BFS) algorithm. We show that $\gamma (G)$ characterizes the connectedness of the graph $G$. We further establish new bounds on $\gamma (G)$, and analyze the graphs that attain extremal values. Finally, we derive an elegant formula for $\gamma (G)$ when $G$ is the Cartesian product of finitely many graphs. Applying this formula, we explicitly compute $\gamma (G)$ for various families of graphs, including hypercube graphs, Hamming graphs, and others.