Distinguishing geometric graphs
Michael O. Albertson, Debra Boutin · Journal of Graph Theory · 2006
Abstract We begin the study of distinguishing geometric graphs. Let G be a geometric graph. An automorphism of the underlying graph that preserves both crossings and noncrossings is called a geometric automorphism. A labeling, f: V(G) → {1, 2, … , r}, is said to be r‐distinguishing if no nontrivial geometric automorphism preserves the labels. The distinguishing number of G is the minimum r such that G has an r‐distinguishing labeling. We show that when Kn is not the nonconvex K4, it can be 3‐distinguished. Furthermore, when n ≥ 6, there is a Kn that can be 1‐distinguished. For n ≥ 4, K2,n can realize any distinguishing number between 1 and n inclusive. Finally, we show that every K3,3 can be 2‐distinguished. We also offer several open questions. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 135–150, 2006