Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.00134 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913969400184832 |
|---|---|
| author | Cruickshank, James Dewar, Sean Kitson, Derek |
| author_facet | Cruickshank, James Dewar, Sean Kitson, Derek |
| contents | 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 $\ell_\infty^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 $\ell_\infty^d$ are odd-hole-free. Connections to redundant rigidity are also presented. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_00134 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algebraic connectivity in normed spaces Cruickshank, James Dewar, Sean Kitson, Derek Combinatorics Metric Geometry Spectral Theory 52C25, 05C50, 05C22, 46B20 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 $\ell_\infty^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 $\ell_\infty^d$ are odd-hole-free. Connections to redundant rigidity are also presented. |
| title | Algebraic connectivity in normed spaces |
| topic | Combinatorics Metric Geometry Spectral Theory 52C25, 05C50, 05C22, 46B20 |
| url | https://arxiv.org/abs/2508.00134 |