Resolvability and the upper dimension of graphs (Q1569967): Difference between revisions

An ordered vertex subset \(W\) of a connected graph \(G\) is resolving when the vectors of distances towards \(W\) are different for all vertices of \(G\). It is a basis, if it is of minimum cardinality, which is then \(\dim(G)\). \(\dim^+(G)\) is the maximal cardinality of a resolving set, no subset of which is resolving. \(\text{res}(G)\) is the smallest \(k\) for which each \(k\)-subset is resolving. It is shown that \(\lceil\log_3(\Delta(G)+1)\rceil \leq \dim(G) \leq \dim^+(G) \leq \text{res}(G)\leq n-1\), where \(\Delta(G)\) denotes the maximum degree among \(G\)'s \(n\) vertices. Also there exist graphs with \(\dim(G)=a\) and \( \text{res}(G)=b\) for any \(2\leq a\leq b\); and also with arbitrary large \(\text{res}(G)-\dim^+(G)\) and \(\dim^+(G)-\dim(G)\). But \(\dim^+(G)= \text{res}(G)=2\) iff \(G\) is a path \(P_n\) (\(n\geq 4\)) or a cycle \(C_n\) (\(n\) odd); and \(\dim^+(G)=n-1\) iff \(G=K_n\).