Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2305.06290 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915838648385536 |
|---|---|
| author | Bifulco, Patrizio Kerner, Joachim |
| author_facet | Bifulco, Patrizio Kerner, Joachim |
| contents | In this note we elaborate on some notions of surface area for discrete graphs which are closely related to the inverse degree. These notions then naturally lead to associated connectivity measures of graphs and to the definition of a special class of large graphs, called social graphs, that might prove interesting for applications. In addition, we derive spectral estimates involving the surface area and, as a main result, present an upper bound on the second eigenvalue for planar graphs which in some cases improves upon existing bounds from D. A. Spielman and S.-H. Teng, Spectral partitioning works: Planar graphs and finite element meshes, and M. Plümer, Upper eigenvalue bounds for the Kirchhoff Laplacian on embedded metric graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_06290 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the surface area of graphs, related connectivity measures and spectral estimates Bifulco, Patrizio Kerner, Joachim Combinatorics Differential Geometry Metric Geometry Spectral Theory 05C50, 05C40, 05C22, 05C90, 05C10 In this note we elaborate on some notions of surface area for discrete graphs which are closely related to the inverse degree. These notions then naturally lead to associated connectivity measures of graphs and to the definition of a special class of large graphs, called social graphs, that might prove interesting for applications. In addition, we derive spectral estimates involving the surface area and, as a main result, present an upper bound on the second eigenvalue for planar graphs which in some cases improves upon existing bounds from D. A. Spielman and S.-H. Teng, Spectral partitioning works: Planar graphs and finite element meshes, and M. Plümer, Upper eigenvalue bounds for the Kirchhoff Laplacian on embedded metric graphs. |
| title | On the surface area of graphs, related connectivity measures and spectral estimates |
| topic | Combinatorics Differential Geometry Metric Geometry Spectral Theory 05C50, 05C40, 05C22, 05C90, 05C10 |
| url | https://arxiv.org/abs/2305.06290 |