A Note on the Decomposition Dimension of Complete Graphs

Abstract

A decomposition \(\mathcal{F} = \{F_1, \ldots, 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) \neq 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) \leq \frac{1}{2} (\log_2 n)^2 (1 + o(1)).\)