Distinguishing maps. II: General case (Q396760)

Summary: A group \(A\) acting faithfully on a set \(X\) has distinguishing number \(k\), written \(D(A,X)=k\), if there is a coloring of the elements of \(X\) with \(k\) colors such that no nonidentity element of \(A\) is color-preserving, and no such coloring with fewer than \(k\) colors exists. Given a map \(M\) with vertex set \(V\) and automorphism group \(\mathrm{Aut}(M)\), let \(D(M)=D(\mathrm{Aut}(M),V)\). If \(M\) is orientable, let \(D^+(M)=D(\mathrm{Aut}^+(M),V)\), where \(\mathrm{Aut}^+(M)\) is the group of orientation-preserving automorphisms. In Part I [Electron. J. Comb. 18, No. 1, Research Paper P50, 21 p. (2011; Zbl 1220.05134)], the author showed there are four maps \(M\) with \(D^+(M)>2\). In this paper, a complete classification is given for the graphs underlying maps with \(D(M)>2\). There are \(31\) such graphs, \(22\) having no vertices of valence 1 or 2, and all have at most \(10\) vertices.