pith. sign in

arxiv: 2605.06837 · v1 · submitted 2026-05-07 · 🧮 math.CO

The strong and doubly metric dimensions of Johnson and Kneser graphs

Jozef Kratica , Mirjana \v{C}angalovi\'c , Vera Kova\v{c}evi\'c-Vuj\v{c}i\'c This is my paper

Pith reviewed 2026-05-11 01:06 UTC · model grok-4.3

classification 🧮 math.CO
keywords Johnson graphKneser graphstrong metric dimensiondoubly metric dimensionresolving setmetric dimensiongraph theorycombinatorics
0
0 comments X

The pith

The exact strong metric dimension of Johnson graphs is obtained from known results, the strong metric dimension of Kneser graphs is found for n at least 3k minus 1, and the doubly metric dimension for k equals 2 is ceiling of 2n over 3 for

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper calculates specific metric dimensions for two families of graphs. It uses previously known results to give the exact strong metric dimension for Johnson graphs. For Kneser graphs, it provides the value under the condition that the number of elements n is at least three times the subset size k minus one. It also proves that the doubly metric dimension for the cases where subsets have size 2 is the same for both graph types and equals the ceiling of twice the number of elements divided by three. These dimensions measure how many landmarks are needed to uniquely locate points in the graph using distances.

Core claim

Using known results from the literature the exact value of the strong metric dimension of the Johnson graph J(n, k) is obtained. The strong metric dimension of the Kneser graph K(n, k) is obtained for n ≥ 3k − 1. It is shown that the doubly metric dimensions of the Johnson graph J(n, 2) and the Kneser graph K(n, 2) are both equal to ⌈2n/3⌉.

What carries the argument

Strong and doubly resolving sets that distinguish vertex pairs by distance inequalities in Johnson and Kneser graphs.

If this is right

  • The strong metric dimension for any Johnson graph J(n,k) follows immediately from literature without new derivations.
  • For Kneser graphs the strong metric dimension is known exactly when n ≥ 3k-1.
  • The doubly metric dimension equals ⌈2n/3⌉ for Johnson and Kneser graphs with k=2.
  • These exact values give the minimal size of sets needed to locate all vertices in the graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The formulas may extend to give the doubly metric dimension for higher values of k.
  • These results could be used to bound similar dimensions in related graphs like other intersection graphs.
  • Small-case verification by computer enumeration would test the doubly metric dimension formula directly.
  • The linear growth in n suggests scaling behavior for large instances of these graphs.

Load-bearing premise

The known results on strong metric dimension can be applied directly to Johnson graphs to get the exact value, and the explicit calculations for the doubly metric dimension hold for the k=2 cases across all n.

What would settle it

Checking a small case such as the Johnson graph J(5,2) by finding the smallest strong resolving set size and seeing whether it matches the value predicted by the literature results used in the paper.

read the original abstract

In this paper, the strong and doubly metric dimensions of Johnson and Kneser graphs are considered. The exact value of the strong metric dimension of Johnson graph $J_{n,k}$ is obtained using the well-known results from the literature. The strong metric dimension of Kneser graph $K_{n,k}$ has been obtained for $n \ge 3k-1$. Finally, it has been shown that the doubly metric dimensions of Johnson graph $J_{n,2}$ and Kneser graph $K_{n,2}$ are both $\lceil \frac{2n}{3} \rceil$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper considers the strong and doubly metric dimensions of Johnson and Kneser graphs. It obtains the exact value of the strong metric dimension of the Johnson graph J_{n,k} using well-known results from the literature. The strong metric dimension of the Kneser graph K_{n,k} is determined for n ≥ 3k-1. It is shown that the doubly metric dimensions of J_{n,2} and K_{n,2} are both ⌈2n/3⌉.

Significance. If the claims hold, the paper provides exact expressions for these graph parameters in two key families of graphs, which is significant for the field of graph theory and metric dimension studies. The approach of leveraging existing results for Johnson graphs is sound in principle, and the conditional result for Kneser graphs along with the specific doubly metric dimension for k=2 cases add new knowledge. These could aid in further research on locating sets and related concepts.

major comments (2)
  1. [Abstract / Johnson graph result] The claim that the exact strong metric dimension of J_{n,k} is obtained using well-known results from the literature (abstract) is load-bearing for the first main result. The manuscript must identify the specific theorems applied and provide a brief verification that their hypotheses hold for the Johnson graph on k-subsets with distance defined by intersection size, for all n > k ≥ 1; without this, direct applicability cannot be confirmed.
  2. [Doubly metric dimension section] The doubly metric dimension claim that both J_{n,2} and K_{n,2} equal ⌈2n/3⌉ (abstract) is a central new result limited to k=2. The full proof in the manuscript should be examined for any unstated assumptions on n that might restrict the range of validity beyond what is claimed.
minor comments (2)
  1. [Abstract] The abstract states results but provides no explicit formulas or values; including the derived expressions (e.g., the strong metric dimension formula for J_{n,k}) would improve readability.
  2. [Kneser graph result] The restriction n ≥ 3k-1 for the Kneser strong metric dimension is stated without discussion of boundary cases or why smaller n are excluded; a short remark on this would clarify the scope.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address each major comment point by point below. Where revisions are needed for clarity, we will incorporate them in the next version.

read point-by-point responses

  1. Referee: [Abstract / Johnson graph result] The claim that the exact strong metric dimension of J_{n,k} is obtained using well-known results from the literature (abstract) is load-bearing for the first main result. The manuscript must identify the specific theorems applied and provide a brief verification that their hypotheses hold for the Johnson graph on k-subsets with distance defined by intersection size, for all n > k ≥ 1; without this, direct applicability cannot be confirmed.

    Authors: We agree that greater specificity is warranted to allow independent verification. In the revised manuscript we will explicitly cite the precise theorems from the literature that are invoked for the strong metric dimension of J_{n,k} and add a short paragraph verifying that their hypotheses are satisfied under the intersection-size distance on the vertex set of k-subsets, for the entire range n > k ≥ 1. This addition will not alter the stated value but will make the dependence on prior results fully transparent. revision: yes

  2. Referee: [Doubly metric dimension section] The doubly metric dimension claim that both J_{n,2} and K_{n,2} equal ⌈2n/3⌉ (abstract) is a central new result limited to k=2. The full proof in the manuscript should be examined for any unstated assumptions on n that might restrict the range of validity beyond what is claimed.

    Authors: We have re-examined the complete proof. The lower-bound constructions and upper-bound arguments rely solely on the standard hypotheses that n ≥ 3 (ensuring the graphs are connected and the vertex sets are non-empty), with no further implicit restrictions on n. The equality ⌈2n/3⌉ holds uniformly for all such n. To preempt any ambiguity we will insert a single clarifying sentence at the opening of the section stating the precise range of validity. revision: partial

Circularity Check

0 steps flagged

Derivation relies on external literature results and explicit case restrictions; no internal reduction to inputs

full rationale

The paper obtains the strong metric dimension of Johnson graphs J_{n,k} by direct appeal to unspecified well-known literature results rather than deriving it internally. The Kneser result is explicitly restricted to n ≥ 3k-1, and the doubly-metric claims are confined to the k=2 case with the value ⌈2n/3⌉ stated as shown. No equations, ansatzes, or self-citations are presented that reduce a claimed prediction or uniqueness statement back to a fitted parameter or prior self-result by construction. The central claims therefore remain externally grounded or case-limited rather than self-referential.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard graph-theoretic definitions and previously established results in the literature, with no new free parameters or postulated entities introduced.

axioms (1)
  • standard math Standard definitions of Johnson graphs J(n,k), Kneser graphs K(n,k), strong metric dimension, and doubly metric dimension.
    These are invoked as background knowledge from graph theory.

pith-pipeline@v0.9.0 · 5422 in / 1268 out tokens · 43804 ms · 2026-05-11T01:06:52.446349+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    P. J. Slater, Leaves of trees, Congr. Numer 14 (549-559) (1975) 37

    work page 1975

  2. [2]

    Harary, R

    F. Harary, R. Melter, On the metric dimension of a graph, Ars Combin 2 (191-195) (1976) 1

    work page 1976

  3. [3]

    Khuller, B

    S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Dis- crete Applied Mathematics 70 (3) (1996) 217–229

    work page 1996

  4. [4]

    A. Sebő, E. Tannier, On metric generators of graphs, Mathematics of Operations Research 29 (2) (2004) 383–393. 12

    work page 2004

  5. [5]

    O. R. Oellermann, J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discrete Applied Mathematics 155 (3) (2007) 356– 364

    work page 2007

  6. [6]

    Kratica, V

    J. Kratica, V. Kovačević-Vujčić, M. Čangalović, N. Mladenović, Strong metric dimension: A survey, Yugoslav Journal of Operations Research 24 (2) (2014) 187–198

    work page 2014

  7. [7]

    Gallai, Uber extreme punkt-und kantenmengen, Annales Universi- tatis Scientiarum Budapestinensis de Rolando Eotvos Nominatae, Sectio Mathematica 2 (1959) 133–138

    T. Gallai, Uber extreme punkt-und kantenmengen, Annales Universi- tatis Scientiarum Budapestinensis de Rolando Eotvos Nominatae, Sectio Mathematica 2 (1959) 133–138

    work page 1959

  8. [8]

    Kuziak, M

    D. Kuziak, M. L. Puertas, J. A. Rodriguez-Velazquez, I. G. Yero, Strong resolving graphs: The realization and the characterization problems, Discrete Applied Mathematics 236 (2018) 270–287

    work page 2018

  9. [9]

    Cáceres, C

    J. Cáceres, C. Hernando, M. Mora, I. Pelayo, M. Puertas, C. Seara, D. Wood, On the metric dimension of Cartesian products of graphs, SIAM Journal in Discrete Mathematics 21 (2) (2007) 423–441

    work page 2007

  10. [10]

    Kratica, M

    J. Kratica, M. Čangalović, V. Kovačević-Vujčić, Computing minimal doubly resolving sets of graphs, Computers & Operations Research 36 (7) (2009) 2149–2159

    work page 2009

  11. [11]

    Kratica, V

    J. Kratica, V. Kovačević-Vujčić, M. Čangalović, A new lower bound for doubly metric dimension and related extremal differences, Filomat 41, arXiv preprint arXiv:2310.06071

    work page arXiv

  12. [12]

    Kelenc, N

    A. Kelenc, N. Tratnik, I. G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension, Discrete Applied Mathematics 251 (2018) 204–220

    work page 2018

  13. [13]

    Kelenc, D

    A. Kelenc, D. Kuziak, A. Taranenko, I. G. Yero, Mixed metric dimension of graphs, Applied Mathematics and Computation 314 (2017) 429–438

    work page 2017

  14. [14]

    González, C

    A. González, C. Hernando, M. Mora, The equidistant dimension of graphs, Bulletin of the Malaysian Mathematical Sciences Society 45 (4) (2022) 1757–1775

    work page 2022

  15. [15]

    R. F. Bailey, J. Cáceres, D. Garioc, A. González, A. Márquez, K. Meagher, M. L. Puertas, Resolving sets for Johnson and Kneser graphs, European Journal of Combinatorics 34 (2013) 736–751. 13

    work page 2013

  16. [16]

    R. F. Bailey, P. Cameron, Base size, metric dimension and other invari- ants of groups and graphs, Bull. Lond. Math. Soc 43 (2011) 209–242

    work page 2011

  17. [17]

    Kratica, M

    J. Kratica, M. Čangalović, V. Kovačević-Vujčić, Equidistant dimen- sion of Johnson and Kneser graphs, Kragujevac Journal of Mathematics 51 (4) (2027) 547–556

    work page 2027

  18. [18]

    Kratica, M

    J. Kratica, M. Čangalović, V. Kovačević-Vujčić, M. Milivojević-Danas, Edge and mixed metric dimension of Johnson graphs, arXiv preprint arXiv:2407.07851

    work page arXiv

  19. [19]

    Kratica, V

    J. Kratica, V. Kovačević-Vujčić, M. Čangalović, M. Stojanović, Mini- mal doubly resolving sets and the strong metric dimension of some con- vex polytopes, Applied Mathematics and Computation 218 (19) (2012) 9790–9801

    work page 2012

  20. [20]

    Valencia-Pabon, J.-C

    M. Valencia-Pabon, J.-C. Vera, On the diameter of Kneser graphs, Dis- crete Mathematics 305 (1-3) (2005) 383–385

    work page 2005

  21. [21]

    Stahl, n-tuple colorings and associated graphs, Journal of Combina- torial Theory, Series B 20 (2) (1976) 185–203

    S. Stahl, n-tuple colorings and associated graphs, Journal of Combina- torial Theory, Series B 20 (2) (1976) 185–203

    work page 1976

  22. [22]

    Erdös, C

    P. Erdös, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford 12 (2) (1961) 313–320

    work page 1961

  23. [23]

    J. Tian, S. Klavžar, Variety of general position problems in graphs, Bulletin of the Malaysian Mathematical Sciences Society 48 (1) (2025) 5

    work page 2025

  24. [24]

    Ullas Chandran S, S

    V. Ullas Chandran S, S. Klavžar, J. Tuite, The general position problem: A survey, arXiv e-prints (2026) arXiv:2501.19385v4. 14

    work page arXiv 2026