Algebraic connectivity in normed spaces

The algebraic connectivity of a graph G in a finite dimensional real normed linear space X is a geometric counterpart to the Fiedler number of the graph and can be regarded as a measure of the rigidity of the graph in X. We analyse the behaviour of the algebraic connectivity of G in X with respect to graph decomposition, vertex deletion and isometric isomorphism, and provide a general bound expressed in terms of the geometry of X and the Fiedler number of the graph. Particular focus is given to the space ℓ∞d where we present explicit formulae and calculations as well as upper and lower bounds. As a key tool, we show that the monochrome subgraphs of a complete framework in ℓ∞d are odd-hole-free. Connections to redundant rigidity are also presented.