Distinguishing numbers of 4-regular quadrangulations on the Klein bottle

graph, concerning the symmetry of graphs as follows. Let G be a graph and c: V (G) → {1, 2,..., d} an assignment of labels to the vertices of G. Such a labeling c is called a d-distinguishing labeling of G if no automorphism of G other than the identity map preserves the labels given by c. A graphG is said to be d-distinguishable if G admits a d-distinguishing labeling. The distinguishing number of G is defined as the minimum number d such that G is d-distinguishable and is denoted by D(G). For examples, the distinguishing number of a complete graph Kn is D(Kn) = n. Negami and Fukuda have found the distinguishing number of 4-regular quad-rangulation on the torus in [2]. Furthermore, Negami [1] has established a general theorem on the distinguishing number of graphs embedded on closed surfaces, us-ing some technique in topological graph theory. In his theory, “the faithfulness of embedding”, defined in [1], plays an important role. Acutually, he has proved that polyhedral graphs faithfully embedded on a closed surface are 2-distinguishable with finitely many exceptions