Distinguishing index of maps
Monika Pilśniak, Thomas W. Tucker · European Journal of Combinatorics · 2019
The distinguishing number of a group A acting on a finite set Ω, denoted by D(A,Ω), is the least k such that there is a k-coloring of Ω which is preserved only by elements of A fixing all points in Ω. For a map M, also called a cellular graph embedding or ribbon graph, the action of Aut(M) on the vertex set V gives the distinguishing number D(M). It is known that D(M)≤2 whenever |V|>10. The action of Aut(M) on the edge set E gives the distinguishing index D′(M), which has not been studied before. It is shown that the only maps M with D′(M)>2 are the following: the tetrahedron; the maps in the sphere with underlying graphs Cn, or K1,n for n=3,4,5; a map in the projective plane with underlying graph C4; two one-vertex maps with 4 or 5 edges; one two-vertex map with 4 edges; or any map obtained from these maps using duality or Petrie duality. There are 39 maps in all.