HEXAGONbeta

Edge multiset dimension of subdivided complete graphs

Primarily AI-generated textHuman understanding: all partsmath.CO — Combinatorics

Contributed by Pedro Machado Manhães de Castro ↗

Version 1 / Oct 26, 2026 / CC BY 4.0

Abstract

An edge of a graph can be identified by its distances to a suitable set of vertices. If the reports omit the names of these vertices, only a multiset of distances remains, and finding a suitable set becomes more difficult. We determine the asymptotic cost of this loss of information for subdivided complete graphs. Let KnK_n be the complete graph on n≥3n\ge3 vertices, and let SL(Kn)S_L(K_n) replace each edge with a path of LL edges, where L≥2L\ge2 is an integer. Let edim⁡m\operatorname{edim}_{\mathrm m} be the minimum number of vertices whose distance multisets distinguish all edges. For every fixed L≥3L\ge3, we prove edim⁡m(SL(Kn))=ΘL ⁣(n1+1/⌊L/2⌋)(n⟶∞). \operatorname{edim}_{\mathrm m}(S_L(K_n))=\Theta_L\!\left(n^{1+1/\lfloor L/2\rfloor}\right) \qquad(n\longrightarrow\infty). Retaining the names requires only Θ(n)\Theta(n) vertices. Without them, the cost is quadratic at length three, has order n3/2n^{3/2} at lengths four and five, and has smaller exponents at longer fixed lengths. We also settle existence at the two shortest lengths for every n≥3n\ge3: no selection works at length two, whereas at length three at most (n2)\binom n2 vertices suffice. The proofs combine a count of integer vectors with realizable vertex labels. Sidon sets distinguish endpoint pairs at odd lengths, and exact finite certificates complete the length-three construction.

Provenance statement

The author directed the research and made substantive use of OpenAI's ChatGPT and Codex as artificial intelligence (AI) tools for literature retrieval, mathematical exploration, code development, symbolic and numerical checks, and manuscript preparation. The author critically assessed this assistance and determined what to incorporate into the work. To refine the English, grammar, and presentation of results, proofs, and figures, the author made revisions directly or specified changes for the tools to implement, critically assessing successive versions as the exposition developed. AI tools also assisted in checking and maintaining the manuscript's internal consistency. The author checked all results and takes full responsibility for the mathematical content and the final manuscript. The author has checked and understood all parts of this contribution.

Tools used

OpenAI
ChatGPT
OpenAI
Codex

References

  1. Cesar O. Aguilar, Anti-regular graphs with loops and their spectrum , 2018, Preprint, revised 2019, arXiv:1805.08287v2 (https://arxiv.org/abs/1805.08287v2).arXiv
  2. Jaan Allikvere, The edge multiset dimension of hypercubes , 2026, Preprint, arXiv:2608.09983v1 (https://arxiv.org/abs/2608.09983v1).arXiv
  3. M. Beck and S. Robins, Computing the continuous discretely: Integer-point enumeration in polyhedra , 2nd ed., Undergraduate Texts in Mathematics, Springer, New York, 2015.
  4. D. Burstein and J. Rubin, Sufficient conditions for graphicality of bidegree sequences , SIAM J. Discrete Math. 31 (2017), no. 1, 50--62.
  5. J. Cilleruelo, Combinatorial problems in finite fields and Sidon sets , Combinatorica 32 (2012), no. 5, 497--511.
  6. Brian Cloteaux, A sufficient condition for graphic sequences with given largest and smallest entries, length, and sum , Discrete Mathematics & Theoretical Computer Science 20 (2018), no. 1, 25.
  7. Pierre Dusart, Inégalités explicites pour ψ(X)\psi(X) , θ(X)\theta(X) , π(X)\pi(X) et les nombres premiers , C. R. Math. Rep. Acad. Sci. Canada 21 (1999), 53--59.
  8. P. Erd ő s and P. Tur á n, On a problem of Sidon in additive number theory, and on some related problems , J. London Math. Soc. 16 (1941), no. 4, 212--215.
  9. M. Farhan, S. Klav ž ar, D. Kuziak, and I. G. Yero, Multiset resolvability parameters in graphs: A survey with new results and open problems , 2026, Preprint, arXiv:2607.10311v1 (https://arxiv.org/abs/2607.10311v1).arXiv
  10. D. R. Fulkerson, Zero-one matrices with zero trace , Pacific J. Math. 10 (1960), no. 3, 831--836.
Show all 16 referencesShow fewer references
  1. H. M. Ikhlaq, R. Ismail, H. M. A. Siddiqui, and M. F. Nadeem, A new technique to uniquely identify the edges of a graph , Symmetry 15 (2023), no. 3, 762.
  2. A. Kelenc, N. Tratnik, and I. G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension , Discrete Appl. Math. 251 (2018), 204--220.
  3. Martin Knor, Riste Š krekovski, and Ismael G. Yero, A note on the metric and edge metric dimensions of 2-connected graphs , Discrete Applied Mathematics 319 (2022), 454--460.
  4. Kostadinka Lapkova, Correction to: Explicit upper bound for the average number of divisors of irreducible quadratic polynomials , Monatshefte für Mathematik 186 (2018), 675--678.
  5. D. Ruiz and C. Trujillo, Construction of Bh[g]B_h[g] sets in product of groups , Rev. Colombiana Mat. 50 (2016), no. 2, 165--174.
  6. I. E. Zverovich and V. E. Zverovich, Contributions to the theory of graphic sequences , Discrete Mathematics 105 (1992), no. 1--3, 293--303.

Version history

  1. v1Submitted by Pedro Machado Manhães de CastroInitial depositCurrentOct 26, 2026