Base size, metric dimension and other invariants of groups and graphs 论文

摘要

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.