On the chromatic dimension of a graph (Q2716522)

The concept of metric dimension of a graph introduced by \textit{F. Harary} and \textit{R. A. Melter} [Ars Comb. 1976, No. 2, 191-195 (1976; Zbl 0349.05118)] (also called location number by \textit{P. J. Slater} [Proc. 6th Southeast. Conf. Comb., Graph Theor., Comput.; Boca Raton 1975, 549-559 (1975; Zbl 0316.05102)]) is studied under the name chromatic dimension. NEWLINENEWLINENEWLINEA (metric or color) basis of a graph \(G\) is a set of vertices \(W\) of minimum size such that for every pair of distinct vertices \(u,v\in V(G)\) there is at least one \(w\in W\) such that the length of a shortest \(u,w\)-path is different from the length of a shortest \(v,w\)-path (in other words \(d(u,w)\neq d(v,w)\)). The metric (or chromatic) dimension of a graph \(G\), denoted by \(\dim(G)\), is the size of such a basis, \(|W|\). It is shown that for any integer \(k\) there is a graph \(G\) with a vertex \(v\) whose removal changes the dimension by \(k\): \(\dim(G)-\dim(G-v)=k\). NEWLINENEWLINENEWLINEThe basis number of a graph \(G\), denoted by \(\text{bas}(G)\), is the maximum value \(r\) such that every set of \(r\) vertices can be extended to a basis. Naturally, \(\text{bas}(G)\leq \dim(G)\), with equality for complete graphs and odd cycles and it remains an open question if there are any other connected graphs for which equality holds. It is shown that \(\text{bas}(T)=0\) for every tree (except \(\text{bas}(K_2)=1\)), and \(\text{bas}(G)\) is determined for cycles and complete multipartite graphs. Finally it is shown that if \(0\leq a\leq b/2\), then there is a graph \(G\) with \(\text{bas}(G)=a\) and \(\dim(G)=b\) and the question of whether this can be extended to all \(0\leq a\leq b\) is posed.