A Note on the Decomposition Dimension of Complete Graphs

Abstract

A decomposition $\mathcal{F}=\{F_1,\dots ,F_r\}$ of the edge set of a graph $G$ is called a resolving $r$-decomposition if for any pair of edges $e_1$ and $e_2$, there exists an index $i$ such that $d(e_1,F_i)\ne d(e_2,F_i)$, where $d(e,F)$ denotes the distance from $e$ to $F$. The decomposition dimension $dec(G)$ of a graph $G$ is the least integer $r$ such that there exists a resolving $r$-decomposition. Let $K_n$ be the complete graph with $n$ vertices. It is proved that $dec(K_n)\le \frac{1}{2}({\log }_{2}n{)}^2(1+o(1)).$