The strong and doubly metric dimensions of Johnson and Kneser graphs

Jozef Kratica, Mirjana Čangalović, Vera Kovačević-Vujčić · 2026

Read The strong and doubly metric dimensions of Johnson and Kneser graphs by Jozef Kratica, Mirjana Čangalović, Vera Kovačević-Vujčić (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06837.txt.

Description

Jozef Kratica, Mirjana Čangalović, and Vera Kovačević-Vujčić determine metric dimensions for two classic graph families, the Johnson and Kneser graphs. A metric dimension counts how few landmark vertices suffice to identify every vertex by its distances to them. The strong version demands unique identification along shortest paths, and the doubly version strengthens the separation requirement further between vertex pairs.

For Johnson graphs the exact strong metric dimension is obtained from known literature results. For Kneser graphs it is settled whenever the ground set is at least roughly triple the subset size. Both families, in the case of two-element subsets, share the same doubly metric dimension, a rounded two-thirds of the vertex count parameter.

Catalog record

CREATORJozef Kratica, Mirjana Čangalović, Vera Kovačević-Vujčić
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06837

Browse the full library · About the Tower of Babel