Some resolving parameters in a class of Cayley graphs

Ali Zafari; Jia-Bao Liu

REVIEW 5 major objections 4 minor 15 references

Some resolving parameters in a class of Cayley graphs

T0 review · 5 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read For every even $n\ge4$, the Cayley graph $\Lambda=\mathrm{Cay}(D_{2n},\Psi)$ has metric dimension $n$, doubly resolving number $n$, and strong metric dimension $2n-2$, and is not distance regular.

desk verdict Plausible values for resolving parameters in a clean Cayley/Toeplitz family, but the lower-bound proofs are missing and Theorem 3.3 is a non sequitur. read the letter →

arxiv 1908.07854 v9 pith:HASB57N3 submitted 2019-08-21 math.CO

Jia-Bao Liu , Ali Zafari This is my paper · ORCID

classification math.CO MSC 05C1205E3005C50

keywords CayleygraphmetricdimensiondoublyresolvingsetstrongToeplitzdihedralgroupdistance-regularcocktail-party

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

Working with the graph $\Lambda=\mathrm{Cay}(D_{2n},\Psi)$ obtained from the dihedral group $D_{2n}$ by taking as connection set every reflection together with the half-turn rotation $a^{n/2}$ (for even $n\ge4$), the paper determines three resolving parameters exactly. The metric dimension is $n$, the minimum size of a doubly resolving set is $n$, and the strong metric dimension is $2n-2$. The same $n$-vertex half-set $R=\{a,\dots,a^{n/2}; ab,\dots,a^{n/2}b\}$ is shown to be both metric and doubly resolving. Along the way the paper shows $\Lambda$ is vertex-transitive but not distance regular, gives its spectrum, and identifies its automorphism group. Exact resolving parameters for non-distance-regular vertex-transitive graphs are comparatively rare, so the value of the paper is a complete answer for a natural infinite family.

What carries the argument

The load-bearing object is the graph $\Lambda=\mathrm{Cay}(D_{2n},\Psi)$ with $\Psi=\{ab,a^2b,\dots,a^{n-1}b,b\}\cup\{a^{n/2}\}$; it has diameter 2 and its complement is the disjoint union of two copies of the cocktail-party graph $CP(n/2)$ (the complete graph on $n/2$ pairs with each pair's edge deleted). The argument runs on the partition of the vertex set into rotations $V_1$ and reflections $V_2$, the half-set $R$, and the fact that distances inside $\Lambda$ are only 1 or 2, which makes distance vectors to $R$ short and explicit. Two structural facts carry the non-metric conclusions: the spectrum $\{n+1,1-n,1^{(n-2)},-1^{(n)}\}$, whose four distinct eigenvalues rule out distance regularity, and the complement's cocktail-party structure, which determines $\mathrm{Aut}(\Lambda)$ as an iterated wreath product $Z_2 \wr \mathrm{Sym}(n/2) \wr \mathrm{Sym}(2)$.

What would settle it

Run an exhaustive search over all subsets of the $2n$ vertices of $\Lambda$ for $n=4$ (the smallest case) and check whether any subset of size $5$ strongly resolves every pair; if yes, the claimed $2n-2=6$ is false. A direct spot-check is whether $a^{n/2+1}$, which lies outside $N$, strongly resolves the adjacent pair $\{a^n,a^{n/2}\}$ by lying on a shortest path from $a^n$ to $a^{n/2+1}$.

Watch

Extended reading notes

Core claim

Let $V_1$ be the rotations and $V_2$ the reflections of $D_{2n}$. The paper's central discovery is that, for even $n\ge4$, the $n$-vertex set $R=\{a,\dots,a^{n/2}; ab,\dots,a^{n/2}b\}$ resolves $\Lambda$: every vertex outside $R$ has a different vector of distances to the vertices of $R$, and the same $R$ also doubly resolves every pair of vertices. The lower bounds are argued by partitioning any candidate resolving set into its intersections with $V_1$ and $V_2$ and showing that unequal sizes, or adjacent vertices inside one half, leave two vertices with identical distance vectors. For strong resolution, the paper contends that deleting any four-vertex clique $N=\{a^n,a^{n/2};a^n b,a^{n/2}b\}$ leaves a set that cannot strongly resolve the pair $\{a^n,a^{n/2}\}$, so every strong resolving set must have size at least $2n-2$. It also computes the adjacency spectrum $\{n+1,1-n,1^{(n-2)},-1^{(n)}\}$ and, since a distance-regular graph of diameter $2$ can have at most three distinct eigenvalues, concludes that $\Lambda$ is not distance regular.

Load-bearing premise

The strong-metric-dimension lower bound depends on the unproved claim that, for the adjacent pair $\{a^n,a^{n/2}\}$ in $V_1$, no vertex outside $\{a^n,a^{n/2},a^n b,a^{n/2}b\}$ can strongly resolve it; if an outside vertex can lie on a shortest path between the two, the value $2n-2$ could be too large.

Editorial extensions

If this is right

For every even $n\ge4$, the family $\Lambda$ is a sharp example where the metric dimension equals the order of the generating half-set: no resolving set of size $n-1$ exists, and $R$ achieves $n$.
The doubly resolving number of $\Lambda$ coincides with its metric dimension, both being $n$, so any minimum metric basis here is automatically minimum doubly resolving.
A four-eigenvalue spectrum forces $\Lambda$ to be non-distance-regular, so the exact resolving parameters are examples in the harder, non-distance-regular setting rather than in the well-understood distance-regular setting.
The automorphism group is explicitly $\mathrm{Aut}(\Lambda)\cong Z_2 \wr \mathrm{Sym}(n/2) \wr \mathrm{Sym}(2)$, which gives a concrete symmetry description of the whole family.
Since $\Lambda$ is isomorphic to the Toeplitz graph $T_{2n}(\{1,3,5,\dots,2n-1;n\})$, the same exact parameters apply to that drawing of the graph.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One could test the strong-metric bound computationally for $n=4,6$: an exhaustive search for strong resolving sets of size less than $2n-2$ would either confirm the claimed pattern or locate a smaller set, giving a concrete check of the proof's lower-bound step.
The construction suggests a wider family: replace the dihedral group by any split group with a similar 'all coset elements plus one central involution' connection set; the same distance-2 argument might yield analogous exact resolving parameters.
Because the complement splits into two cocktail-party graphs, the metric and resolving behaviour may be governed by a product-like structure; exploring whether $R$ and $V(\Lambda)-R$ always form complementary resolving sets could give a transfer principle for other Cayley graphs whose complements are disjoint unions.

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.

Desk Editor's Note

read the letter

Here's a quick read. The graph family is a genuine, simple object: two n-sets V1 and V2 with all cross edges, plus a perfect matching inside each part (which makes the complement two cocktail-party graphs). What the paper does well: the construction is clean, the automorphism-group observation in Prop. 3.2 is nice, and the small examples check out. The explicit resolving set in Theorem 3.1 — the first half of V1 and the first half of V2 — is an honest, verifiable upper bound.

The soft spots are in the lower bounds. Theorem 3.1 never rules out a resolving set of size n−1; it only shows some size-n sets fail. Theorem 3.2's Case 3 says 'by Theorem 3.1, V−R is also resolving' — that does not imply R is doubly resolving for the pair you need. And Theorem 3.3 is a genuine non sequitur: showing that S=V−N is not a strong resolving set for one 4-clique N only proves that a strong resolving set must meet N. It neither constructs a strong resolving set of size 2n−2 nor proves a lower bound. The stress-test note is accurate.

Minor issues: the spectrum in Prop. 3.1 is asserted by reference to a similar proof in another paper, and several 'we may assume' moves in the case analyses are not justified by automorphisms, though they are likely fixable. The self-citation pattern is not itself a problem, but key facts are delegated to the authors' own earlier work.

Bottom line: the claims may all be true, and this is a natural little family, but the manuscript does not establish them. I would not send this version to a referee. I'd tell the authors to repair the lower bounds and resubmit. If all you want is to know whether the values are correct, a referee could check that quickly, but that's not the same as the paper being ready.

Referee Report

5 major / 4 minor

Summary. The paper considers the Cayley graph Λ = Cay(D_{2n}, Ψ) on the dihedral group D_{2n}, where n is even and n ≥ 4, with generating set Ψ = {ab, a^2b, ..., a^{n-1}b, b} ∪ {a^{n/2}}. It claims that Λ is not distance regular, determines its automorphism group, and computes three resolving parameters: metric dimension n (Theorem 3.1), cardinality of a minimum doubly resolving set n (Theorem 3.2), and strong metric dimension 2n-2 (Theorem 3.3). The paper also gives two small examples for n = 6 illustrating the metric-dimension statements.

Significance. If the results are correct, they provide exact values of three resolving parameters for a concrete infinite family of Cayley/Toeplitz graphs, and they contrast ordinary metric dimension with strong metric dimension in a diameter-2 setting. The claimed values are plausible, and the n = 6 examples in the paper are consistent with the metric-dimension claims. However, the proofs as written contain substantial gaps: no valid lower bound is produced for any of the three main theorems, and the proof of the strong metric dimension result is essentially a non sequitur. The paper would be a useful contribution if these gaps are repaired, but in its current form the central claims are not established.

major comments (5)

[Theorem 3.1 (metric dimension)] The proof never establishes the lower bound β(Λ) ≥ n. Cases 1 and 2 only show that certain n-element sets are not resolving, and Case 3 exhibits one n-element resolving set; no argument rules out resolving sets of cardinality n−1. A missing argument would use the fact that for each i, the pair {a^i, a^{i+n/2}} in V1 (and similarly in V2) is resolved only by one of the two vertices themselves, since every vertex in V2 is at distance 1 from both and every other vertex in V1 is at distance 2 from both. As written, the conclusion that the metric dimension is n does not follow.
[Theorem 3.1, Case 3] The reduction 'We may assume R1 = {a, a^2, ..., a^{n/2}}' is not justified. It requires an automorphism of Λ mapping an arbitrary independent half-set of V1 to the standard half-set; the paper does not prove this transitivity (it may be derivable from Proposition 3.2, but the derivation is absent). The same unproved normalization is used again in Theorem 3.2.
[Theorem 3.2 (doubly resolving set)] The proof gives no lower bound: it attempts to show only that one particular n-element set R is doubly resolving, and even that demonstration is incomplete. In Case 3, the statement that 'by Theorem 3.1, V(Λ)−R is also a resolving set' does not imply that R doubly resolves two vertices outside R: double resolution requires x, y ∈ R with d(u,x)−d(u,y) ≠ d(v,x)−d(v,y), and a resolving vertex lying outside R cannot be used for this purpose. The normalization 'We may assume' for the representative pairs is also not proved.
[Theorem 3.3 (strong metric dimension)] The proof establishes only that the particular set S = V(Λ)−N, with N = {a^n, a^{n/2}, a^n b, a^{n/2} b}, is not a strong resolving set. This shows that a strong resolving set must contain at least one vertex of N; it does not rule out strong resolving sets of size 2n−3 and it does not construct a strong resolving set of size 2n−2. The final sentence 'From the above cases, we can be concluded...' is therefore a non sequitur. A valid proof would need structural lemmas characterizing, for diameter-2 vertices, which third vertices strongly resolve a given pair, and then a matching construction of a strong resolving set of size 2n−2.
[Proposition 3.1 (non-distance-regularity)] The spectrum {n+1, 1−n, 1^{(n−2)}, −1^{(n)}} is asserted by analogy with Proposition 11 of [12]; no eigenvalues or eigenvectors for Λ are computed in this manuscript. Since the four-eigenvalue count is the entire evidence for non-distance-regularity, this assertion is not supported within the paper, and it cannot be checked without reproducing the cited proof in the present setting.

minor comments (4)

[References] Reference [15] points to 'https://arxiv.org/submit/3838712', a submission URL rather than a citable published item; it should be replaced by the final published version or removed.
[Throughout] There are many typographical corruptions (for example, '/nequal' instead of ≠, and exponent expressions such as 'a^{n+2i\over 2}' without parentheses). The manuscript needs a careful proofreading pass before it can be published.
[Abstract] The abstract promises that the class 'cannot be edge transitive', but the body contains no proof of non-edge-transitivity; either prove this claim or remove it from the abstract.
[Proposition 3.2] The automorphism group statement is asserted with a brief reference to [14] and a computation of the complement; for completeness, the composite wreath-product notation should be expanded, since this statement is later used implicitly in the normalization steps of Theorems 3.1 and 3.2.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the resolving-parameter values are attacked by direct distance-vector computations, the self-citations are background or independent known facts, and the Theorem 3.3 gap is a proof omission rather than an equivalence-by-construction.

full rationale

I find no circularity in the derivation chain. Theorem 3.1 constructs an explicit n-vertex resolving set and argues the lower bound directly from distance representations and adjacencies inside V1 and V2; no fitted quantity is later renamed as a prediction. Theorem 3.2 inherits the lower bound because every doubly resolving set is also a resolving set, so the previously established metric dimension n is legitimate input, not a circular equivalent. Proposition 3.1 invokes a spectrum computation 'by a similar way' to the authors' earlier paper [12], but that is a cited method rather than an imported target result, and Proposition 3.2 uses the standard cocktail-party/circulant isomorphism from [13]; both are externally checkable facts that do not contain the theorems being proved. Reference [15] is the paper's own preprint URL, but it is not used as load-bearing evidence. The main genuine deficiency is in Theorem 3.3: the proof tests only one particular (2n-4)-vertex set S = V(Lambda)-N, shows S is not a strong resolving set, then concludes 'the minimum cardinality of a strong resolving set for Lambda must be 2n-2.' This does not construct a strong resolving set of size 2n-2 and does not rule out a strong resolving set of size 2n-3, so the concluding inference is an omitted proof step. That is a correctness gap, not a circular reduction, and no self-definition, fitted-input renaming, or self-citation chain forces the claimed value. Accordingly the circularity score is 0.

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

The paper's claims rest on standard graph theory theorems plus unproved structural assertions about diameter, spectrum, and automorphism group. No free parameters or invented entities are present; the graph family is constructed, not fitted.

assumptions (4)

domain assumption The adjacency spectrum of Λ is {n+1, 1-n, 1^(n-2), -1^(n)}.
Used in Proposition 3.1 to infer four distinct eigenvalues; the text defers to 'a similar way' in [12] instead of deriving it.
domain assumption Λ has diameter 2.
Stated at the start of Proposition 3.1 as 'not hard to see'; it underlies all distance computations in Theorems 3.1-3.3.
standard math A connected distance-regular graph with diameter d has exactly d+1 distinct eigenvalues.
Invoked in Proposition 3.1 to conclude Λ is not distance regular; this is standard distance-regular graph theory.
domain assumption The complement of Λ is the disjoint union of two copies of CP(n/2), so Aut(Λ) is the stated wreath product.
Used in Proposition 3.2; relies on references [13,14] and on unstated isomorphism checks.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Some resolving parameters in a class of Cayley graphs." pith.science (2026). https://pith.science/paper/HASB57N3

@misc{pith2026190807854,
  author       = {Pith},
  title        = {Pith review of: Some resolving parameters in a class of Cayley graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HASB57N3}},
  note         = {Machine review of arXiv:1908.07854}
}

abstract

Resolving parameters is a fundamental area of combinatorics with applications not only to many branches of combinatorics but also to other sciences. In this article, we construct a class of Toeplitz graphs, and will be denoted by $T_{2n}(W)$, so that they are Cayley graphs. First, we review some of the features of this class of graphs. In fact, this class of graphs are vertex transitive, and by calculating the spectrum of the adjacency matrix related with them, we show that this class of graphs cannot be edge transitive. Moreover, we show that this class of graphs cannot be distance regular, and since the computing resolving parameters of a class of graphs such that are not distance regular is more difficult, then we regard this as justification for our focus on some resolving parameters. In particular, we determine the minimal resolving set, doubly resolving set and strong metric dimension for this class of graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[12]

S. M. Mirafzal and A. Zafari, An Interesting Property of a Class of Circulant Graphs , Journal of Mathematics, vol. 2017, pp.1-4, 2017

work page 2017
[1]

Godsil and G

C. Godsil and G. Royle, Algebraic graph theory, Springer, New Y ork, 2001

work page 2001
[2]

Harary and R

F. Harary and R. A. Melter, On the metric dimension of a graph , Combinatoria, vol. 2, pp.191-195, 1976

work page 1976
[3]

P . J. Slater, Leaves of trees, in Proceedings of the 6th Southeastern Conference on Combin atorics, Graph theory and Computing , Boca Raton, FL, USA, pp.549-559, 1975

work page 1975
[4]

R. F. Bailey and P . J. Cameron, Base size, metric dimension and other invariants of groups a nd graphs, Bulletin of the London Mathematical Society, vol. 43, pp.209-242, 2011

work page 2011
[5]

Beerliova, F

Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Ho ﬀmann, M. Mihal´ ak, and L. Shankar Ram,Network discovery and veriﬁcation , IEEE J. Sel. Area. Commun, vol. 24, pp.2168-2181, 2006

work page 2006
[6]

J.-B. Liu, M. F. Nadeem, H. M. A. Siddiqui, and W. Nazir, Computing Metric Dimension of Certain Families of Toeplitz Graphs, IEEE Access, vol. 7, pp.126734-126741, 2019

work page 2019
[7]

van Dal, G

R. van Dal, G. Tijssen, Z. Tuza, J. A. A. van der V een, C. Zam ﬁrescu, and T. Zamﬁrescu, Hamiltonian properties of Toeplitz graphs, Discrete Math, vol. 159, pp.69-81, 1996

work page 1996

Show all 15 references

[8]

J.-B. Liu, A. Zafari, and H. Zarei, Metric Dimension, Minimal Doubly Resolving Sets, and the St rong Metric Dimension for Jellyﬁsh Graph and Cocktail Party Graph, Complexity, vol. 2020, pp.1-7, 2020

2020
[9]

A. E. Brower, A. M. Cohen, and A. Neumaier, Distance Regular Graphs, Springer, Berlin, 1989

1989
[10]

C´ aceres, C

J. C´ aceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Pue rtas, C. Serra, and D. R. Wood, On the metric dimension of Cartesian products of graphs, SIAM Journal on Discrete Mathematics, vol. 21(2), pp.423-441, 2007

2007
[11]

Seb¨ o and E

A. Seb¨ o and E. Tannier, On metric generators of graphs , Math. Oper . Res, vol. 29(2), pp.383-393, 2004

2004
[13]

S. M. Mirafzal and A. Zafari, On the spectrum of a class of distance-transitive graphs , Electronic Journal of Graph Theory and Applications, vol. 5(1), pp.63-69, 2017

2017
[14]

Frucht, On the groups of repeated graphs, Bulletin of the American Ma thematical Society, vol.55, pp.418–420, 1949

R. Frucht, On the groups of repeated graphs, Bulletin of the American Ma thematical Society, vol.55, pp.418–420, 1949

1949
[15]

Liu and A

J.-B. Liu and A. Zafari, Some algebraic properties and metrics for a class of Toeplit z graphs , Preprint is at https://arxiv.org/submit/3838712. 5

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [12]

S. M. Mirafzal and A. Zafari, An Interesting Property of a Class of Circulant Graphs , Journal of Mathematics, vol. 2017, pp.1-4, 2017

work page 2017

[2] [1]

Godsil and G

C. Godsil and G. Royle, Algebraic graph theory, Springer, New Y ork, 2001

work page 2001

[3] [2]

Harary and R

F. Harary and R. A. Melter, On the metric dimension of a graph , Combinatoria, vol. 2, pp.191-195, 1976

work page 1976

[4] [3]

P . J. Slater, Leaves of trees, in Proceedings of the 6th Southeastern Conference on Combin atorics, Graph theory and Computing , Boca Raton, FL, USA, pp.549-559, 1975

work page 1975

[5] [4]

R. F. Bailey and P . J. Cameron, Base size, metric dimension and other invariants of groups a nd graphs, Bulletin of the London Mathematical Society, vol. 43, pp.209-242, 2011

work page 2011

[6] [5]

Beerliova, F

Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Ho ﬀmann, M. Mihal´ ak, and L. Shankar Ram,Network discovery and veriﬁcation , IEEE J. Sel. Area. Commun, vol. 24, pp.2168-2181, 2006

work page 2006

[7] [6]

J.-B. Liu, M. F. Nadeem, H. M. A. Siddiqui, and W. Nazir, Computing Metric Dimension of Certain Families of Toeplitz Graphs, IEEE Access, vol. 7, pp.126734-126741, 2019

work page 2019

[8] [7]

van Dal, G

R. van Dal, G. Tijssen, Z. Tuza, J. A. A. van der V een, C. Zam ﬁrescu, and T. Zamﬁrescu, Hamiltonian properties of Toeplitz graphs, Discrete Math, vol. 159, pp.69-81, 1996

work page 1996