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$.