The Distinguishing Numbers of Triangulations on the Projective Plane

摘要

The distinguishing number of a graph G is defined as the minimum number d such that G admits an assignment of d distinct labels to vertices which cannot be preserved by any automorphism of G except the identity map. We shall prove that the distinguishing number of triangulations on the projective plane takes only five values 1, 2, 3, 4 and 6 and characterize the structures attaining these values.