\documentclass[11pt,a4paper]{article}
\usepackage[margin=27mm]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{booktabs,array,microtype,needspace,flafter}
\usepackage[font=small,labelfont=bf]{caption}
\usepackage{placeins}
\usepackage{algorithm}
\usepackage{algpseudocode}
\floatname{algorithm}{Algorithm}
\renewcommand{\thealgorithm}{\arabic{algorithm}}
\algrenewcommand\algorithmicrequire{\textbf{Input:}}
\algrenewcommand\algorithmicensure{\textbf{Output:}}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,calc,decorations.pathreplacing,positioning,matrix}
\usepackage[sort,compress]{cite}
\usepackage[hidelinks]{hyperref}
\usepackage{orcidlink}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\edimm}{\operatorname{edim}_{\mathrm m}}
\newcommand{\edim}{\operatorname{edim}}
\newcommand{\Fp}{\mathbb F_p}
\newcommand{\F}{\mathbb F}
\newcommand{\Z}{\mathbb Z}
\newcommand{\ind}{\mathbf1}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\sgn}{sgn}
\emergencystretch=1em
\renewcommand{\topfraction}{.9}
\renewcommand{\bottomfraction}{.8}
\renewcommand{\textfraction}{.08}
\renewcommand{\floatpagefraction}{.72}
\makeatletter
\setlength{\@fptop}{0pt}
\setlength{\@fpsep}{18pt}
\setlength{\@fpbot}{0pt plus 1fil}
\makeatother
\hypersetup{pdftitle={Edge multiset dimension of subdivided complete graphs},pdfauthor={Pedro M. M. de Castro},pdfsubject={Sharp asymptotic bounds, Sidon sets, and distance histograms},pdfkeywords={Edge multiset dimension; graph subdivision; Sidon set; degree sequence; incidence matrix}}
\title{Edge multiset dimension of subdivided complete graphs}
\author{Pedro M. M. de Castro\,\orcidlink{0000-0002-9470-7458}\\
\small Centro de Inform\'atica, Universidade Federal de Pernambuco\\
\small Recife, Pernambuco, Brazil\\
\small \texttt{pmmc@cin.ufpe.br}}
\date{October 26, 2026}
\begin{document}
\maketitle

\begin{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 \(K_n\) be the complete
graph on \(n\ge3\) vertices, and let \(S_L(K_n)\) replace
each edge with a path of \(L\) edges, where \(L\ge2\) is an integer.
Let \(\edimm\)
be the minimum number of vertices whose distance multisets distinguish
all edges. For every fixed \(L\ge3\), we prove
\[
 \edimm(S_L(K_n))=\Theta_L\!\left(n^{1+1/\lfloor L/2\rfloor}\right)
 \qquad(n\longrightarrow\infty).
\]
Retaining the names requires only \(\Theta(n)\) vertices. Without them,
the cost is quadratic at length three, has order \(n^{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\ge3\): no selection works at length two, whereas at length three
at most \(\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.

\end{abstract}


\medskip
\noindent\textbf{Keywords:} Edge multiset dimension; graph subdivision; Sidon set; degree sequence; incidence matrix.

\smallskip
\noindent\textbf{Mathematics Subject Classification (2020):} Primary 05C12; Secondary 05C07, 11B13.


\input{sections/introduction}
\input{sections/geometry}
\input{sections/lower_bounds}
\input{sections/symmetric}
\input{sections/odd}
\input{sections/short_lengths}
\subsection{Certifying the remaining orders}\label{sec:certificates}
\input{sections/certificates}
\FloatBarrier
\section{Finite existence and restrictions on the selection}\label{sec:quantitative}
\input{sections/quantitative}
\FloatBarrier
\section{Conclusion and further questions}\label{sec:conclusion}
\input{sections/conclusion}

\medskip
\noindent\textbf{AI-use disclosure.}
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.

\appendix
\input{sections/analytic_three}
\input{sections/realization}
\input{sections/supp_exact}
\input{sections/supp_symmetric}
\input{sections/uniform}
\input{sections/refinements}
\input{sections/biased_selection}
\FloatBarrier
\small

\input{bibliography}
\end{document}