Metric dimension and maximum eigenvalue multiplicity of graph Laplacians
Abstract
We study equality between metric dimension and the maximum eigenvalue multiplicity of the Laplacian and signless Laplacian matrices. These quantities are not ordered in general. Using the standard decomposition associated with twin classes, we separate forced multiplicities from quotient-spectrum contributions. We give complete equality classifications for complete multipartite graphs and core--satellite graphs, and enumerate the multipartite equality graphs by order. For graphs formed by attaching at least two leaves to every vertex of a connected core, the metric dimension and the multiplicity of the eigenvalue $ 1 $ are known; we show that this multiplicity is maximal for both matrices, and uniquely maximal except for $ P_3 $. We enumerate this core--leaf family up to isomorphism and obtain a uniform asymptotic formula by order and metric dimension, together with the quadratic exponential growth rate $ 1/18 $. An exact census of connected graphs of orders two through seven identifies the first separating examples and examples without twins. Finally, for every odd $ r \in \mathbb{Z}_{\geq 3} $, we study $ Θ_{2, 2, r} $ and determine both maximum multiplicities: the two equality properties alternate with $ r $ modulo four, producing infinite separating families in both directions.
Related
- The metric Zariski multiplicity conjecture in dimension 4
- Weak k-metric dimension of Hamming graphs: rectangular products and near-maximum parameters
- How the eigenvalue region of standardized Laplacians leaves the 2005 polygon
- Spectral stability of empirical metric-measure Laplacians
- Mixed local-nonlocal eigenvalue problems in the Heisenberg group: spectral theory and singular multiplicity
BibTeX
@misc{alfuraidan2026metric,
title = {{Metric dimension and maximum eigenvalue multiplicity of graph Laplacians}},
author = {Monther Rashed Alfuraidan and Suliman Khan and Lorenzo Sauras Altuzarra},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26875},
eprint = {2610.26875},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26875},
}
RIS
TY - UNPB
TI - Metric dimension and maximum eigenvalue multiplicity of graph Laplacians
AU - Monther Rashed Alfuraidan
AU - Suliman Khan
AU - Lorenzo Sauras Altuzarra
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.26875
UR - https://arxiv.org/abs/2610.26875
AB - We study equality between metric dimension and the maximum eigenvalue multiplicity of the Laplacian and signless Laplacian matrices. These quantities are not ordered in general. Using the standard decomposition associated with twin classes, we separate forced multiplicities from quotient-spectrum contributions. We give complete equality classifications for complete multipartite graphs and core--satellite graphs, and enumerate the multipartite equality graphs by order. For graphs formed by attaching at least two leaves to every vertex of a connected core, the metric dimension and the multiplicity of the eigenvalue $ 1 $ are known; we show that this multiplicity is maximal for both matrices, and uniquely maximal except for $ P_3 $. We enumerate this core--leaf family up to isomorphism and obtain a uniform asymptotic formula by order and metric dimension, together with the quadratic exponential growth rate $ 1/18 $. An exact census of connected graphs of orders two through seven identifies the first separating examples and examples without twins. Finally, for every odd $ r \in \mathbb{Z}_{\geq 3} $, we study $ Θ_{2, 2, r} $ and determine both maximum multiplicities: the two equality properties alternate with $ r $ modulo four, producing infinite separating families in both directions.
ER -