Pith. sign in

REVIEW 5 minor 32 references

Localization and metric dimension for families of highly structured digraphs

T0 review · 0 major / 5 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Highly structured digraphs have small localization numbers and metric dimensions: O(√n log n) for asymmetric normally regular digraphs, and O(log n) for certain team tournaments.

desk verdict Clean directed adaptation of Babai that delivers the first general O(√n log n) and O(log n) bounds for several design-theoretic digraph families. read the letter →

arxiv 2607.05152 v1 pith:L4HGVWY3 submitted 2026-07-06 math.CO

Robert F. Bailey , Brittany Pittman This is my paper · ORCID
classification math.CO MSC 05C1205C2005C69
keywords metricdimensionlocalizationnumbernormallyregulardigraphsdoublytournamentsteamdistinguishingsetsDeza
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper adapts Babai’s 1980 probabilistic method for resolving sets of undirected strongly regular graphs to directed analogues defined by common out-neighbours. It shows that the localization number and metric dimension of an asymmetric normally regular digraph on n vertices are at most O(√n log n), provided every pair of vertices has a positive number of common out-neighbours. The same argument yields O(log n) bounds for nearly doubly regular tournaments and for a class of doubly regular team tournaments. These upper bounds matter because they guarantee that a short list of distance probes can uniquely identify any vertex in these highly regular directed networks, just as in the classical undirected setting.

What carries the argument

A probabilistic existence lemma (Lemma 2.1) that produces a distinguishing set of size O(n log n/c) whenever every pair of vertices has symmetric difference of in-neighbourhoods at least c; the size c is then lower-bounded by √n-1 for ANRDs via the NRD parameter equation and a hypergraph intersection argument.

What would settle it

Exhibit a single asymmetric normally regular digraph on n ≥ 108 vertices with λ, μ > 0 in which two vertices have in-neighbourhoods whose symmetric difference is smaller than √n-1; the O(√n log n) bound then fails for that graph.

Watch

Extended reading notes

Core claim

For any asymmetric normally regular digraph D on n ≥ 108 vertices with positive parameters λ, μ, the localization number and metric dimension satisfy ζ(D) 孍im(D) 孌eil(2n log n/(√n-1)), hence are O(√n log n). For doubly regular (m,r)-team tournaments of type II the bound improves to O(log n).

Load-bearing premise

The claim that every pair of vertices in an asymmetric normally regular digraph with positive parameters has in-neighbourhoods whose symmetric difference is at least the square root of the number of vertices.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper adapts Babai’s 1980 probabilistic method for distinguishing sets of undirected strongly regular graphs to several families of highly structured digraphs. After establishing a general existence lemma (Lemma 2.1) that produces a distinguishing set of size O(n log n / c) whenever every pair of vertices has in-neighbourhood symmetric difference at least c, the authors obtain concrete upper bounds on both metric dimension and localization number. The main results are: for an asymmetric normally regular digraph ANRD(n,k,λ,μ) with λ,μ>0 and n≥108 one has ζ(D)≤dim(D)≤⌈2n log n/(√n-1)⌉=O(√n log n) (Theorem 2.6); the same O(log n) bound holds for nearly doubly regular tournaments (Theorem 2.11) and for doubly regular (m,r)-team tournaments of type II (Theorem 2.15). Parallel but weaker bounds are derived for ordinary graphs, Deza digraphs and divisible design digraphs.

Significance. The work supplies the first systematic upper bounds on metric dimension and localization number for the principal directed analogues of strongly regular graphs. The O(√n log n) result for ANRDs and the sharper O(log n) results for the two tournament families are natural directed counterparts of Babai’s classical estimates and of the known bounds for Paley graphs and doubly regular tournaments. The proofs are self-contained, rely only on standard parameter equations and a classical hypergraph intersection lemma, and cleanly separate the general probabilistic engine from the family-specific estimates of |N⁻(u)△N⁻(v)|. The paper therefore both extends the undirected theory and provides a reusable template for other digraph families defined by common-neighbour conditions.

minor comments (5)
  1. In the abstract and the final sentence of the introduction the authors write “common out-neighbours”, yet all subsequent arguments (Lemma 2.1, the definition of distinguishing sets, and every application) work exclusively with in-neighbourhoods N⁻. A single clarifying sentence would remove the inconsistency.
  2. Theorem 2.2 states the bound in terms of t=min{λ,μ,2λ-μ}, while the paragraph immediately following correctly notes that for ANRDs one may take t=max{λ,μ}. The two statements are compatible but the switch of min/max is easy to miss; a parenthetical remark would help.
  3. The threshold n≥108 in Theorem 2.6 is only needed to guarantee √n-1>2 log n so that Lemma 2.1 applies. It would be useful to record the (slightly weaker) bound that holds for all n≥4 once the ceiling function is taken into account.
  4. Figure 1 is a Cayley digraph of Q8; the caption and the surrounding text correctly identify it as an NRD(8,3,1,0), but the figure itself does not label the digons, which may confuse a reader unfamiliar with the quaternion group.
  5. A few typographical slips: “cope probe” (p. 2), “orG” (p. 2), and the missing space before “and” in the definition of ordinary graphs (p. 7).

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the O(√n log n) and O(log n) bounds follow from a self-contained probabilistic lemma plus external parameter equations and Babai’s hypergraph intersection lemma.

full rationale

The central engine is Lemma 2.1, a direct probabilistic counting argument that produces a distinguishing set of size ⌈2n log n/c⌉ whenever every pair of vertices has in-neighbourhood symmetric difference at least c>2 log n; the proof is written out in full and does not rely on any prior result of the authors. All subsequent theorems simply supply a concrete lower bound on that symmetric difference (from the definition of the digraph family or from published parameter equations of Jørgensen and of Babai) and invoke Lemma 2.1. Lemma 2.5, the only non-trivial estimate, uses the classical NRD equation (Lemma 2.3, cited from Jørgensen) together with Babai’s hypergraph lemma (Lemma 2.4) and elementary double-counting; none of these steps is definitional or fitted. Self-citations appear only for background (metric-dimension surveys, earlier localization results on tournaments) and are not load-bearing for the new bounds. Consequently the derivation chain is independent of the authors’ own earlier claims and contains no circular reduction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters and no new physical or combinatorial entities. It rests entirely on the classical probabilistic method, Babai's hypergraph intersection lemma, and the already-published parameter equations that define the digraph families under study.

assumptions (4)
  • standard math Probabilistic method: a random set of size ⌈2n log n/c⌉ is a distinguishing set with positive probability whenever every pair of vertices has in-neighbourhood symmetric difference at least c>2 log n (Lemma 2.1).
    Direct adaptation of Babai's 1980 counting argument; the expectation calculation is elementary and fully written.
  • standard math Babai's hypergraph lemma: a nonempty regular r-uniform hypergraph on n vertices in which every two edges intersect in at least d points satisfies r^{2}>nd (Lemma 2.4).
    Cited from Babai 1980 and used only to force k>√(nd) inside the proof of Lemma 2.5.
  • domain assumption Parameter equation for NRDs: 2kλ+(n-2k-1)μ=k^{2}-k (Lemma 2.3, from Jørgensen).
    Taken as given from the literature that defines normally regular digraphs; used to obtain the lower bound k≥√n-1 when λ,μ≥1.
  • domain assumption Definitions and parameter relations for Deza digraphs, divisible design digraphs, nearly doubly regular tournaments and doubly regular team tournaments of type II (from Wang-Feng, Crnković-Kharaghani, Jørgensen et al.).
    The paper works inside these already-defined families; the only new work is verifying the neighbourhood-difference hypothesis for each family.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Localization and metric dimension for families of highly structured digraphs." pith.science (2026). https://pith.science/paper/L4HGVWY3

@misc{pith2026260705152,
  author       = {Pith},
  title        = {Pith review of: Localization and metric dimension for families of highly structured digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L4HGVWY3}},
  note         = {Machine review of arXiv:2607.05152}
}
abstract

We investigate metric dimension and the localization game for several families of directed analogues of strongly regular graphs and their generalizations, adapting a probabilistic method of Babai (1980) for bounding the size of resolving sets in undirected strongly regular graphs. We derive upper bounds on the localization number and metric dimension depending on the order of the graph and the maximum number of common out-neighbours for a pair of vertices. We consider normally regular digraphs, so-called "ordinary graphs", classes of Deza digraphs, divisible design digraphs, nearly doubly regular tournaments, and certain doubly regular team tournaments. In particular, for asymmetric normally regular digraphs on $n$ vertices, we show that these invariants are bounded above by $O(\sqrt{n} \log n)$, and improve this to $O(\log n)$ for a class of doubly regular team tournaments.

Figures

Figures reproduced from arXiv: 2607.05152 by the authors.

Figure 1
Figure 1. This Cayley digraph of the quaternion group [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. A (6, 2, 0, 1)-Deza digraph The following upper bound on the metric dimension and localization number of Deza digraphs is an immediate consequence of Lemma 2.1. The proof is almost identical to that of Theorem 2.2. Theorem 2.9. Let D be a (n, k, a, b)-Deza digraph. If k − b > log(n) then ζ(D) ≤ dim(D) ≤ ⌈n log n/(k − b)⌉. We also consider a generalization of DRADs known as divisible design digraphs. We say that a k-… view at source ↗
Figure 3
Figure 3. A nearly doubly regular tournament of order 9. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: A doubly regular (4, 2)-team tournament of type II. Let di(x) denote the number of out-neighbours in Vi of a vertex x. Any doubly regular (m, r)- team tournament of type II has the following properties. Lemma 2.12. [22, Theorem 4.3] Let D be a doubly regular (m, r)-tea…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references

  1. [1]

    M. O. Albertson and K. L. Collins, Symmetry breaking in graphs,Electron. J. Combin.3 (1996), #P1.18 (17 pp)

    1996

  2. [2]

    Babai, On the complexity of canonical labeling of strongly regular graphs,SIAM J

    L. Babai, On the complexity of canonical labeling of strongly regular graphs,SIAM J. Comput. 9(1980), 212–216

    1980

  3. [3]

    R. F. Bailey, On the metric dimension of incidence graphs,Discrete Math.341(2018), 1613– 1619

    2018

  4. [4]

    R. F. Bailey and P. J. Cameron, Base size, metric dimension and other invariants of groups and graphs,Bull. London Math. Soc.43(2011), 209–242

    2011

  5. [5]

    Bensmail, F

    J. Bensmail, F. Mc Inerney and N. Nisse, Metric dimension: from graphs to oriented graphs Electron. Notes Theor. Comp. Sci.346(2019), 111–123

    2019

  6. [6]

    L. M. Blumenthal,Theory and Applications of Distance Geometry, Clarendon Press, Oxford, 1953

    1953

  7. [7]

    Bonato,An Invitation to Pursuit-Evasion Games and Graph Theory, American Mathemat- ical Society, Providence, 2022

    A. Bonato,An Invitation to Pursuit-Evasion Games and Graph Theory, American Mathemat- ical Society, Providence, 2022

    2022

  8. [8]

    Bonato, R

    A. Bonato, R. Cushman, T. G. Marbach and B. E. Pittman, The localization game on oriented graphs,Discrete Appl. Math.338(2023), 145–157

    2023

Show all 32 references
  1. [9]

    A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Springer, New York, 2012

    2012

  2. [10]

    Carraher, I

    J. Carraher, I. Choi, M. Delcourt, L. H. Erickson and D. B. West, Locating a robber on a graph via distance queries,Theoret. Comp. Sci.463(2012), 54–61. 12

    2012

  3. [11]

    Chartrand, M

    G. Chartrand, M. Raines and P. Zhang, The directed distance dimension of oriented graphs, Math. Bohem.125(2000), 155–168

    2000

  4. [12]

    N. E. Clarke, D. Cox, C. Duffy, D. Dyer, S. L. Fitzpatrick and M.-E. Messinger, Limited visibility Cops and Robber,Discrete Appl. Math.282(2020), 53–64

    2020

  5. [13]

    Crnkovi´ c and H

    D. Crnkovi´ c and H. Kharaghani, Divisible design digraphs, inAlgebraic Design Theory and Hadamard Matrices, Springer, Cham, 2015, pp. 43–60

    2015

  6. [14]

    Crnkovi´ c, H

    D. Crnkovi´ c, H. Kharaghani and A.ˇSvob, Divisible design Cayley digraphs,Discrete Math.344 (2020), 111784 (8pp)

    2020

  7. [15]

    A. M. Duval, A directed graph version of strongly regular graphs,J. Combin. Theory Ser. A 47(1988), 71–100

    1988

  8. [16]

    Fijavˇ z and B

    G. Fijavˇ z and B. Mohar, Rigidity and separation indices of Paley graphs,Discrete Math.289 (2004), 157–161

    2004

  9. [17]

    Fossorier, J

    M. Fossorier, J. Jeˇ zek, J. B. Nation and A. Pogel, Ordinary graphs and subplane partitions, Discrete Math.282(2004), 137–148

    2004

  10. [18]

    Harary and R

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

    1976

  11. [19]

    Ito, Doubly regular asymmetric digraphs,Discrete Math.72(1988), 181–185

    N. Ito, Doubly regular asymmetric digraphs,Discrete Math.72(1988), 181–185

    1988

  12. [20]

    L. K. Jørgensen,On normally regular digraphs, Report R 94-2023, Department of Mathematics and Computer Science, Aalborg University (1994)

    2023

  13. [21]

    L. K. Jørgensen, Normally regular digraphs,Electron. J. Combin.22(2015), no. 4, #P4.21 (30 pp)

    2015

  14. [22]

    L. K. Jørgensen, G. A. Jones, M. H. Klin and S. Y. Song, Normally regular digraphs, association schemes and related combinatorial structures,S´ em. Lothar. Combin.71(2014), Article B71c (39 pp)

    2014

  15. [23]

    J. W. Kalk,Sparse ordinary graphs, Ph.D. thesis, University of Hawai‘i, 2005

    2005

  16. [24]

    R. J. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph,Discrete Math.43 (1983), 235–239

    1983

  17. [25]

    Quilliot,Jeux et pointes fixes sur les graphes, Ph.D

    A. Quilliot,Jeux et pointes fixes sur les graphes, Ph.D. thesis, Universit´ e de Paris VI, 1978

    1978

  18. [26]

    K. B. Reid and E. Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices,J. Combin. Theory Ser. A12(1972), 332–338

    1972

  19. [27]

    Seager, Locating a robber on a graphDiscrete Math.312(2012), 3265–3269

    S. Seager, Locating a robber on a graphDiscrete Math.312(2012), 3265–3269

    2012

  20. [28]

    Seager, Locating a backtracking robber on a tree,Theoret

    S. Seager, Locating a backtracking robber on a tree,Theoret. Comp. Sci.539(2014), 28–37

    2014

  21. [29]

    P. J. Slater, Leaves of trees,Congr. Numer.14(1975), 549–568

    1975

  22. [30]

    R. C. Tillquist, R. M. Frongillo and M. E. Lladser, Getting the lay of the land in discrete space: a survey of metric dimension and its applications,SIAM Review65(2023), 919–962

    2023

  23. [31]

    Wang and Y

    K. Wang and Y. Feng, Deza digraphs,European J. Combin.27(2006), 995–1004

    2006

  24. [32]

    Zhang and K

    G. Zhang and K. Wang, A directed version of Deza graphs—Deza digraphs,Australas. J. Combin.28(2003), 239–244. 13

    2003

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.