×

The metric dimension of small distance-regular and strongly regular graphs. (English) Zbl 1321.05287

Summary: A resolving set for a graph \(\Gamma\) is a collection of vertices \(S\), chosen so that for each vertex \(v\), the list of distances from \(v\) to the members of \(S\) uniquely specifies \(v\). The metric dimension of \(\Gamma\) is the smallest size of a resolving set for \(\Gamma\).
A graph is distance-regular if, for any two vertices \(u\), \(v\) at each distance \(i\), the number of neighbours of \(v\) at each possible distance from \(u\) (i.e. \(i-1\), \(i\) or \(i+1\)) depends only on the distance \(i\), and not on the choice of vertices \(u\), \(v\). The class of distance-regular graphs includes all distance-transitive graphs and all strongly regular graphs.
In this paper, we present the results of computer calculations which have found the metric dimension of all distance-regular graphs on up to 34 vertices, low-valency distance transitive graphs on up to 100 vertices, strongly regular graphs on up to 45 vertices, rank-3 strongly regular graphs on under 100 vertices, as well as certain other distance-regular graphs.

MSC:

05E30 Association schemes, strongly regular graphs
PDFBibTeX XMLCite
Full Text: arXiv Link