Small label classes in 2-distinguishing labelings

Debra L. Boutin

Abstract


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.

Keywords


Graph, distinguishing labeling, automorphism group

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.31.d93

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