The Decomposition Dimension of Graphs
For an ordered $k$-decomposition $\cD = \{G_1, G_2, \cdots, G_k\}$
of a connected graph $G$ and an edge $e$ of $G$, the
$\cD$-representation of $e$
is the $k$-tuple
$r(e | \cD)$ = ($d(e, G_1),$ $d(e, G_2),$ $\cdots,$
$d(e, G_k)$),
where $d(e, G_i)$ is the distance from $e$ to $G_i$. A decomposition
$\cD$ is resolving if every two distinct edges of $G$ have distinct
representations.
The minimum $k$ for which $G$ has a resolving $k$-decomposition
is its decomposition dimension $\dec(G)$.
It is shown that for every two positive integers $k$ and $n \geq 2$,
there exists a tree $T$ of order $n$ with $\dec(T) = k$. It is also shown
that $\dec(G) \leq n$ for every graph $G$ of order $n \geq 3$ and
that $\dec(K_n) \leq \lfloor{(2n+5)/3}\rfloor$ for $n \geq 3$.