Small label classes in 2-distinguishing labelings

Debra L. Boutin


A graph G is said to be 2-distinguishable if there is a labeling of the vertices with two labels so that only the trivial automorphism preserves the labels. Call the minimum size of a label class in such a labeling of G the cost of 2-distinguishing G and denote it by ρ(G). This paper shows that for n ≥ 5, ⌈log2n ⌉ + 1 ≤ ρ(Qn) ≤ 2⌈log2n⌉ − 1, where Qn is the hypercube of dimension n.


Graph, distinguishing labeling, automorphism group

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications