zbMATH — the first resource for mathematics

Base size, metric dimension and other invariants of groups and graphs. (English) Zbl 1220.05030
Summary: The base size of a permutation group, and the metric dimension of a graph, are two of a number of related parameters of groups, graphs, coherent configurations and association schemes. They have been repeatedly redefined with different terminology in various different areas, including computational group theory and the graph isomorphism problem. We survey results on these parameters in their many incarnations, and propose a consistent terminology for them. We also present some new results, including on the base sizes of wreath products in the product action, and on the metric dimension of Johnson and Kneser graphs.

05C12 Distance in graphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05E30 Association schemes, strongly regular graphs
20B05 General theory for finite permutation groups
Full Text: DOI