Resolvability and the upper dimension of graphs

DOI10.1016/S0898-1221(00)00126-7MaRDI QIDQ1569967zbMATH OpenFDO

Authors Ping Zhang, Gary Chartrand, Christopher Poisson

Publication date 15 January 2001

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0898-1221(00)00126-7

zbMATH Keywords

metric dimension resolving number resolving set upper dimension

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35)

Review text

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\).

Recommendations

Cites work

Cited in

(75)

This page was built for publication: Resolvability and the upper dimension of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1569967)