Distinguishing actions of symmetric groups and related graphs

2020/09/19 by Mariusz Grech, Grech, Mariusz, Andrzej Kisielewicz +1
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Group Theory (math.GR) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2009.09275

openalex publication_date 2020/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The distinguishing number D(G,X) of an action of a group G on a set X is the least size of a partition of X such that no element of G acting nontrivially on X preserves this partition. In this paper we describe the distinguishing numbers for all actions of the symmetric group S_n, for any n≥ 3. This allows us to describe the distinguishing numbers for all graphs whose automorphism group is isomorphic with a symmetric group. Our description solves a few open problems posed by various authors in earlier papers on this topic.

Related

• Distinguishing numbers for graphs and groups
• Distinguishing simple groups
• Distinguishing Numbers and Generalizations
• The distinguishing number of groups based on the distinguishing number of subgroups
• The distinguishing number of the direct product and wreath product action