Distinguishing maps. II: General case

Thomas W. Tucker¹

¹Colgate University

The electronic journal of combinatorics, Tome 20 (2013) no. 2

Résumé

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 $Aut(M)$, let $D(M)=D(Aut(M),V)$. If $M$ is orientable, let $D^+(M)=D(Aut^+(M),V)$, where $Aut^+(M)$ is the group of orientation-preserving automorphisms. In a previous paper, 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.

Détail

DOI : 10.37236/3410

Classification : 05E18, 05C10, 05C15
Mots-clés : distinguishing number, maps