pith. sign in

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

The partition dimension and k-domination number of a family of non-distance regular graph

Ali Zafari , Saeid Alikhani This is my paper

Pith reviewed 2026-05-13 01:19 UTC · model grok-4.3

classification 🧮 math.CO
keywords partition dimensionk-domination numberToeplitz graphnon-distance-regular graphresolving partitiondominating set
0
0 comments X

The pith

The partition dimension and k-domination number of the Toeplitz graph family T_{2n}(W) are computed exactly.

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

The paper examines the Toeplitz graph T_{2n}(W), a family of non-distance-regular graphs. It defines a resolving partition of the vertices such that every pair of distinct vertices has a unique distance vector to the parts of the partition, and takes the partition dimension to be the smallest number of parts in any such partition. It likewise defines a k-dominating set as a vertex subset in which every vertex outside the set is adjacent to at least k members of the set, and takes the k-domination number to be the size of the smallest such set. The work supplies explicit values for both parameters on T_{2n}(W), closing a gap left by earlier results on other resolving parameters for the same graphs.

Core claim

The authors compute the partition dimension pd(T_{2n}(W)) and the k-domination number γ_k(T_{2n}(W)) for every member of the family of Toeplitz graphs T_{2n}(W).

What carries the argument

The Toeplitz graph T_{2n}(W) constructed from a fixed set W of integers, whose adjacency is determined by differences belonging to W.

If this is right

  • The exact values can be substituted into any algorithm or bound that uses partition dimension or k-domination on these graphs.
  • Earlier results on other metric parameters of T_{2n}(W) can now be combined with these two quantities.
  • The same direct-computation approach may be applied to obtain the parameters on other explicitly described non-distance-regular graphs.

Where Pith is reading between the lines

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

  • The formulas may simplify the analysis of location problems on graphs whose adjacency is governed by a fixed difference set W.
  • The results suggest that the partition dimension remains bounded while the domination number grows linearly with n for this construction.
  • Similar closed-form computations might be feasible for other Toeplitz-like graphs defined by arithmetic progressions or modular conditions.

Load-bearing premise

The standard definitions of a resolving partition and a k-dominating set apply directly to every graph in the Toeplitz family T_{2n}(W) without hidden structural exceptions.

What would settle it

An exhaustive search on a small concrete instance, such as T_4(W) for a specific W, that yields a resolving partition smaller than the value claimed for the partition dimension.

read the original abstract

A partition $\Sigma = \{S_1, S_2, \dots, S_k\}$ of the vertex set $V(G)$ is a resolving partition if every pair of distinct vertices in $G$ has a unique representation relative to $\Sigma$. The partition dimension, $pd(G)$, is the minimum cardinality of such a partition. Additionally, a subset $D \subseteq V(G)$ is a $k$-dominating set if every vertex in $V(G) \setminus D$ has at least $k$ neighbors in $D$; the $k$-domination number, $\gamma_k(G)$, denotes the minimum size of such a set. Determining these parameters is NP-complete and particularly challenging for non-distance-regular graphs. This paper consider the Toeplitz graph $T_{2n}(W)$, a family of non-distance-regular graphs. While some resolving parameters for this family have been established, its partition dimension and $k$-domination number remain unknown. We close this gap by computing both parameters for $T_{2n}(W)$.

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

0 major / 2 minor

Summary. The manuscript studies the Toeplitz graph family T_{2n}(W) of non-distance-regular graphs. It computes the partition dimension pd(T_{2n}(W)) and the k-domination number γ_k(T_{2n}(W)), providing explicit values or closed forms that were previously unknown, thereby closing a gap left by earlier results on other resolving parameters for this family.

Significance. Exact computations of these NP-complete parameters for an infinite family of graphs supply concrete benchmarks and examples that can support further theoretical work on resolving sets and domination in non-distance-regular graphs. The results are potentially useful for testing general algorithms or conjectures about how these parameters behave outside the distance-regular case.

minor comments (2)
  1. Title: 'non-distance regular graph' should read 'non-distance-regular graphs' to match the description of a family.
  2. Abstract: 'This paper consider' is a grammatical error and should be 'This paper considers'.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work on the partition dimension and k-domination number of the Toeplitz graphs T_{2n}(W), for recognizing its significance in providing exact values for an infinite family of non-distance-regular graphs, and for recommending minor revision. No specific major comments were included in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The provided abstract and claim structure contain no equations, parameter fits, self-definitions, or load-bearing self-citations. The paper states that it computes pd(T_{2n}(W)) and γ_k(T_{2n}(W)) for the given Toeplitz family using standard definitions of resolving partitions and k-dominating sets. These are applied directly to the graph construction without any reduction of a 'prediction' back to an input fit, renaming of known results, or invocation of a uniqueness theorem from the authors' prior work. The derivation chain is therefore self-contained and independent of the target quantities.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are described in the abstract; the computation presumably rests on standard graph-theoretic definitions.

pith-pipeline@v0.9.0 · 5487 in / 961 out tokens · 41549 ms · 2026-05-13T01:19:43.836373+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

20 extracted references · 20 canonical work pages

  1. [1]

    Beerliova, F

    Z. Beerliova, F. Eberhard, T. Erlebach et al.,Network discovery and verifica- tion, IEEE J. Sel. Areas Commun.,24(12) (2006), 2168–2181

    work page 2006

  2. [2]

    Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge (1974), second edition (1993)

    N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge (1974), second edition (1993)

    work page 1974

  3. [3]

    Borowiecki and M

    M. Borowiecki and M. Kuzak, On thek-stable andk-dominating sets of graphs, in: Graphs, Hypergraphs and Block Systems, Proc. Symp. Zielona Gora 1976, ed. by M. Borowiecki, Z. Skupieri, L. Szamkolowicz, Zielona Gora 1976. 10

    work page 1976

  4. [4]

    C´ aceres, C

    J. C´ aceres, C. Hernando, M. Mora et al., On the metric dimension of Cartesian products of graphs,SIAM J. Discrete Math.,21(2) (2007), 423–441

    work page 2007

  5. [5]

    Chartrand, E

    G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequ. Math.,59(1-2) (2000), 45–54

    work page 2000

  6. [6]

    Chvatal, Mastermind,Combinatorica,3(3-4) (1983), 325–329

    V. Chvatal, Mastermind,Combinatorica,3(3-4) (1983), 325–329

    work page 1983

  7. [7]

    M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Teory of NP-Completeness, Freeman, New York, NY, USA, 1979

    work page 1979

  8. [8]

    Godsil and G

    C. Godsil and G. Royle,Algebraic Graph Theory, Springer, New York, (2001)

    work page 2001

  9. [9]

    Halmos,A Hilbert Space Problem Book, American Book Company 1967

    P. Halmos,A Hilbert Space Problem Book, American Book Company 1967

    work page 1967

  10. [10]

    Harary and R

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

    work page 1976

  11. [11]

    Harary and A

    F. Harary and A. Schwenk, Which graphs have integral spectra?, Lect. Notes Math.,Springer Verlag,406(1974), 45-50

    work page 1974

  12. [12]

    M. A. Johnson, Structure-activity maps for visualizing the graph variables aris- ing in drug design,J. Biopharm. Stat.,3(1993), 203–236

    work page 1993

  13. [13]

    M. A. Johnson, Browsable structure-activity datasets, Advances in Molecular Similarity, pp. 153–170, JAI Press Connecticut, Stamford, CT, USA, 1998

    work page 1998

  14. [14]

    R. A. Melter and I. Tomescu, Metric bases in digital geometry,Computer Vi- sion, Graphics, and Image Processing,25(1) (1984), 113–121

    work page 1984

  15. [15]

    Ore, Theory of Graphs, Amer Math

    O. Ore, Theory of Graphs, Amer Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence, RI), 1962

    work page 1962

  16. [16]

    Queena Fredlina and E

    K. Queena Fredlina and E. Tri Baskoro, The Partition Dimension of Some Families of Trees,Procedia Computer Science,74(2015), 60–66

    work page 2015

  17. [17]

    J. A. Rodr´ ıguez-Vel´ azquez, I. G. Yero and D. Kuziak, The partition dimension of corona product graphs,Ars Combin.,127(2016), 387–399

    work page 2016

  18. [18]

    J. B. Liu and A. Zafari,Some resolving parameters in a class of Cayley graphs, Journal of Mathematics.2022, 1-8, 2022

    work page 2022

  19. [19]

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

    work page 1975

  20. [20]

    Zafari and S

    A. Zafari and S. Alikhani, The partition dimension andk-domination number of two specific graphs,Journal of Algebraic Systems,14(2)(2026), 331–342. 11

    work page 2026