On \(k\)-dimensional graphs and their bases (Q1410436): Difference between revisions

For an order set \(W=\{w_1,w_2,\dots,w_k\}\) of vertices and a vertex \(v\) in a connected graph \(G\), the representation of \(v\) with respect to \(W\) is the ordered \(k\)-tuple \(r(v|W)=(d(v,w_1),\dots,d(v,w_k))\), where \(d(x, y)\) denotes the distance between the vertices \(x\) and \(y\). The set \(W\) is a resolving set for \(G\) if every two vertices of \(G\) have distinct representations. A resolving set of minimum cardinality \(k\) is called a basis for \(G\) and \(k\) is its dimension. (The inspiration for this topic stems from chemistry.) The authors investigate how the dimension of a connected graph can be affected by the addition of a vertex, and they present a formula for the dimension of a wheel. Furthermore, it is shown that for every integer \(k\geq 2\), there exists a \(k\)-dimensional graph with a unique basis, and that for every pair \(r\), \(k\) of integers with \(k\geq 2\) and \(0\leq r\leq k\), there exists a \(k\)-dimensional graph \(G\) such that there are exactly \(r\) vertices that belong to every basis of \(G\).