\section{Introduction}

Distances from a few observation vertices can identify an unknown edge
of a network. Each observation vertex, called a \emph{landmark},
reports its distance to the nearer endpoint of the edge. Kelenc,
Tratnik and Yero~\cite{kelenc} introduced the edge metric dimension
to measure the smallest number of landmarks needed for this task.
Their starting point was that a set distinguishing all vertices can
still leave two edges indistinguishable. Identifying connections
therefore requires its own choice of observation vertices.

The usual record associates each distance with the landmark that
supplied it. If this association is lost, the values and their
repetitions form a multiset. Ikhlaq et al.~\cite{ikhlaq} introduced
edge multiset dimension to study identification from these records.
The graph and the landmark set remain known.
Their results include families where a small selection suffices and
families where no selection works. This raises two questions: when
does losing the names make identification impossible, and when it
remains possible, how many additional landmarks are required?

We study these questions on subdivisions of complete graphs.
For integers \(n\ge3\) and \(L\ge2\), let \(K_n\) be the complete graph
on \(n\) vertices, and let \(S_L(K_n)\) replace every edge of \(K_n\)
with a path of \(L\) edges. The replacement paths have disjoint
internal vertices. We call the inherited vertices \emph{original}
and the others \emph{internal}. Lengthening the paths adds observation
positions while preserving the symmetry among the originals, so this
family separates the freedom to place landmarks from the difficulty
of distinguishing equivalent parts of the graph.

Subdivisions already serve as examples for comparing distance
identification parameters. Knor, \v{S}krekovski and
Yero~\cite[Proposition 2.5]{knor} determined the named-distance
minimum for \(S_2(K_n)\), which grows linearly with \(n\), in their
study of vertex and edge identification in 2-connected graphs.
For multiset records, the survey of Farhan et
al.~\cite[Section 6.1]{farhan} gives computed values for small
subdivisions and asks whether \(S_2(K_n)\) has no resolving set for
every \(n\ge3\)~\cite[Problem 24]{farhan}.
These results leave a broader issue: how does the replacement length
affect both existence and the cost of identification without names?

Consider \(S_3(K_5)\), with 25 vertices and 30 edges
(Fig.~\ref{fig:information-loss}). Choose the five originals as
landmarks. A middle edge is one step from the two originals at the
ends of its path and four steps from the other three.
The two reports equal to one identify the path when their names are
retained. Once the names are removed, all ten middle edges give
\(\{1,1,4,4,4\}\). The record still identifies the middle position,
leaving ten possibilities for the path.

Choosing more vertices does not by itself settle this ambiguity.
If every vertex is selected, a permutation of the five originals
still exchanges paths while preserving the selection.
A successful choice must break this symmetry and distinguish all
30 edges. Ten suitably placed landmarks achieve this, as the construction
in Section~\ref{sec:three-matrix} will show.\footnote{\raggedright An interactive demonstration of distance reports and landmark choices is available at \url{https://www.cin.ufpe.br/~pmmc/demos/edge-multiset/}.}

\begin{figure}[htbp]
\centering\input{figures/information_loss.tex}
\caption{Losing the names of the landmarks in \(S_3(K_5)\).
In (a), the five filled vertices are selected; the highlighted middle
edges are different. In (b), each is one step from the original vertices
at the ends of its replacement path.
Every other original vertex is four steps away. In (c), the two ordered
records become the same multiset. Crossings without a vertex do not
join paths.}
\label{fig:information-loss}
\end{figure}

\Needspace{10\baselineskip}
We now make the measurement precise. Throughout, graphs are finite,
simple, connected and unweighted. For a graph \(G\) with vertex set
\(V(G)\) and edge set \(E(G)\), let \(d(u,v)\) denote the number of
edges in a shortest path between vertices \(u,v\in V(G)\).
For an edge \(e=xy\in E(G)\) and a vertex \(s\in V(G)\), put
\[
 d(e,s)=\min\{d(x,s),d(y,s)\}.
\]
Fig.~\ref{fig:subdivision-measurement} illustrates the replacement
length and this distance on an expanded path.

A landmark set \(W\subseteq V(G)\) is \emph{edge multiset resolving}
if the multisets \(\{d(e,s):s\in W\}\) differ for every two distinct
edges \(e,f\in E(G)\). Each selected vertex contributes one entry;
equal distances retain their repetitions.
The least size of such a set is the \emph{edge multiset dimension}
\(\edimm(G)\), with value \(\infty\) if no such set exists.
Retaining the names of the landmarks instead gives the
\emph{edge metric dimension} \(\edim(G)\).
In both definitions, each vertex may be selected at most once.

\begin{figure}[htbp]
\centering\input{figures/subdivision_measurement.tex}
\caption{Replacement length and distance to an edge.
In (a), the same original edge \(uv\) is replaced by paths of two,
three and five edges. This operation is applied to every edge of
\(K_5\), keeping its five original vertices.
In (b), the circled vertices form \(W=\{s_1,s_2,s_3\}\), and
\(e=xy\) is the highlighted edge on a length-five path.
The distances from \(e\) to \(s_1,s_2,s_3\) are two, one and two,
respectively, giving \(\{1,2,2\}\). Filled vertices are original.}
\label{fig:subdivision-measurement}
\end{figure}

\Needspace{14\baselineskip}
\begin{theorem}\label{thm:main}
For every \(n\ge3\),
\[
 \edimm(S_2(K_n))=\infty,
 \qquad \edimm(S_3(K_n))\le\binom n2.
\]
For every fixed integer \(L\ge3\),
\[
 \edimm(S_L(K_n))=
 \Theta_L\!\left(n^{1+1/\lfloor L/2\rfloor}\right)
 \qquad\text{as }n\longrightarrow\infty,
\]
where the constants and the sufficient order may depend on \(L\).
\end{theorem}
The lower bound is proved in Section~\ref{sec:lower}, the matching
constructions for \(L\ge4\) in Sections~\ref{sec:symmetric}
and~\ref{sec:odd}, and the two short-length statements in
Section~\ref{sec:short}, including its finite certificates.
The first statement answers the length-two question above.
Length three then marks a change in existence at every order:
a suitable selection always exists, and its minimum size grows
quadratically in \(n\).

At lengths four and five the minimum has order \(n^{3/2}\), at
lengths six and seven it has order \(n^{4/3}\), and longer fixed
lengths give smaller exponents. With the landmark names retained,
only \(\Theta(n)\) vertices are needed at every length
(Proposition~\ref{prop:ordered}).
Thus the theorem gives matching bounds for the cost of losing
correspondence throughout this family, beyond the previously
computed finite cases. It also identifies how additional positions
along the paths reduce that cost.

The lower bound comes from comparing edges next to the same original
vertex. After accounting for the choices on each edge's own path,
the changing part depends on landmark counts in the first half of
the other endpoint's paths. Many different count vectors require
many selected vertices. For an upper bound, we choose these
vectors and realize them by selecting internal vertices.
The middle edge of an odd-length path sees the sum of its two endpoint
vectors, so these sums must identify the pair. Sidon sets supply this
property. Length three requires a separate matrix construction,
completed at the remaining finite orders by exact certificates.
Section~\ref{sec:quantitative} gives finite existence ranges and
quantifies restrictions on the available landmark positions.
The corresponding refinements use exact lattice counts, label
constructions and probabilistic bounds, developed in
Appendices~\ref{supp:exact}--\ref{app:refinements}.