On the metric dimension of a graph (Q1265351)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the metric dimension of a graph |
scientific article; zbMATH DE number 1203579
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the metric dimension of a graph |
scientific article; zbMATH DE number 1203579 |
Statements
On the metric dimension of a graph (English)
0 references
2 December 1998
0 references
The metric dimension of a graph is the minimal order of a subset such that for any pair of vertices of the graph it contains a vertex which is at a different distance to them both. It is shown that in a graph of metric dimension \(k\), any subgraph of order \(2^k+1\) must have more than \(2^{k-1}-1\) missing edges to be complete.
0 references
vertex distance
0 references
metric dimension
0 references
landmark
0 references
0.9598497
0 references
0.9582865
0 references
0 references
0.9549519
0 references
0 references
0.9487683
0 references
0 references
0.9471216
0 references
