2025/07/29 by M. Rajesh Kannan, Rahul Roy, Kannan, M. Rajesh +1
Mathematics · #05C12 #05C50 #05C76 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C12 #msc:05C50 #msc:05C76
paper · pdf · doi:10.48550/arxiv.2507.22015
arxiv created 2026/08/03 · arxiv updated 2026/08/04
The algebraic connectivity of a graph, defined as the second smallest eigenvalue of its Laplacian matrix, admits a well-known variational characterization involving the ℓ2-norm. Motivated by the recent introduction of its ℓ_∞-analogue by Andrade and Dahl, we investigate the graph parameter γ(G), obtained by replacing the ℓ2-norm with the ℓ_∞-norm in the corresponding optimization problem. We establish a simple and explicit combinatorial formula expressing γ(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 γ(G) characterizes graph connectivity and completely characterize all ℓ_∞-Fiedler vectors as the vectors \±(1-γ(G)d(u,⋅)):u∈ M(G)\, where M(G) denotes the set of vertices of maximum transmission. Furthermore, we derive bounds for γ(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 γ(G) under Cartesian products of graphs, leading to explicit expressions for important graph families such as hypercubes, Hamming graphs, grid graphs, and torus graphs.