On the decomposition dimension of trees

AbstractA decomposition F={F1,F2,…,Fr} of the edge set of a graph G is called a resolving r-decomposition if for any pair of edges e1 and e2, there exists an index i such that d(e1,Fi)≠d(e2,Fi), 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. It is proved that for any k⩾3 and r⩾⌈log2k⌉+1, there exists a tree T such that the maximum degree of T is k and dec(T) is r. The relation between the decomposition dimension and the diameter of a tree is also discussed