The connectivity dimension of a graph
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913987732439040 |
|---|---|
| author | Gottwald, Kurt Klement Hofmann, Tobias |
| author_facet | Gottwald, Kurt Klement Hofmann, Tobias |
| contents | This article investigates the connectivity dimension of a graph. We introduce this concept in analogy to the metric dimension of a graph, providing a graph parameter that measures the heterogeneity of the connectivity structure of a graph. We fully characterize extremal examples and present explicit constructions of infinitely many graphs realizing any prescribed non-extremal connectivity dimension. We also establish a general lower bound in terms of the graph's block structure, linking the parameter to classical notions from graph theory. Finally, we prove that the problem of computing the connectivity dimension is NP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09336 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The connectivity dimension of a graph Gottwald, Kurt Klement Hofmann, Tobias Combinatorics Discrete Mathematics 05C40, 05C42, 05C10 This article investigates the connectivity dimension of a graph. We introduce this concept in analogy to the metric dimension of a graph, providing a graph parameter that measures the heterogeneity of the connectivity structure of a graph. We fully characterize extremal examples and present explicit constructions of infinitely many graphs realizing any prescribed non-extremal connectivity dimension. We also establish a general lower bound in terms of the graph's block structure, linking the parameter to classical notions from graph theory. Finally, we prove that the problem of computing the connectivity dimension is NP-complete. |
| title | The connectivity dimension of a graph |
| topic | Combinatorics Discrete Mathematics 05C40, 05C42, 05C10 |
| url | https://arxiv.org/abs/2508.09336 |