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

M. Rajesh Kannan, Rahul Roy · 2025

Read On the l ∞ l_{\infty} -analog of Algebraic Connectivity by M. Rajesh Kannan, Rahul Roy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22015.txt.

Description

Rajesh Kannan and Rahul Roy study a variant of algebraic connectivity. That graph value gauges how well linked a network is. In the classic form it is the second smallest eigenvalue of the graph Laplacian. It has a form based on the two-norm. A recent variant swaps that norm for the maximum norm. It defines a new value whose sense was unclear.

The team sets out a simple formula for the new value in plain graph terms. It equals the order of the graph divided by its maximum transmission. That is the largest sum of distances from any one vertex. They prove it marks graph connectivity. They also describe its Fiedler vectors in full. A product formula for Cartesian products gives values for hypercubes, Hamming graphs, and torus grids.

Catalog record

CREATORM. Rajesh Kannan, Rahul Roy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-22015

Browse the full library · About the Tower of Babel