Throttling for metric dimension and its variants
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_ | 1866908571693744128 |
|---|---|
| author | Brimkov, Boris Diao, Peter Geneson, Jesse Reinhart, Carolyn Tsai, Shen-Fu Wang, William Worley, Kyle |
| author_facet | Brimkov, Boris Diao, Peter Geneson, Jesse Reinhart, Carolyn Tsai, Shen-Fu Wang, William Worley, Kyle |
| contents | Metric dimension is a graph parameter that has been applied to robot navigation and finding low-dimensional vector embeddings. Throttling entails minimizing the sum of two available resources when solving certain graph problems. In this paper, we introduce throttling for metric dimension, edge metric dimension, and mixed metric dimension. In the context of vector embeddings, metric dimension throttling finds a low-dimensional, low-magnitude embedding with integer coordinates. We show that computing the throttling number is NP-hard for all three variants. We give formulas for the throttling numbers of special families of graphs, and characterize graphs with extremal throttling numbers. We also prove that the minimum possible throttling number of a graph of order $n$ is $Θ\left(\frac{\log{n}}{\log{\log{n}}}\right)$, while the minimum possible throttling number of a tree of order $n$ is $Θ(n^{1/3})$ or $Θ(n^{1/2})$ depending on the variant of metric dimension. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_00530 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Throttling for metric dimension and its variants Brimkov, Boris Diao, Peter Geneson, Jesse Reinhart, Carolyn Tsai, Shen-Fu Wang, William Worley, Kyle Combinatorics Discrete Mathematics Metric dimension is a graph parameter that has been applied to robot navigation and finding low-dimensional vector embeddings. Throttling entails minimizing the sum of two available resources when solving certain graph problems. In this paper, we introduce throttling for metric dimension, edge metric dimension, and mixed metric dimension. In the context of vector embeddings, metric dimension throttling finds a low-dimensional, low-magnitude embedding with integer coordinates. We show that computing the throttling number is NP-hard for all three variants. We give formulas for the throttling numbers of special families of graphs, and characterize graphs with extremal throttling numbers. We also prove that the minimum possible throttling number of a graph of order $n$ is $Θ\left(\frac{\log{n}}{\log{\log{n}}}\right)$, while the minimum possible throttling number of a tree of order $n$ is $Θ(n^{1/3})$ or $Θ(n^{1/2})$ depending on the variant of metric dimension. |
| title | Throttling for metric dimension and its variants |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2510.00530 |