Labeling of Sets Under the Actions of \(\overrightarrow{{S}_{n}} \) and \(\overrightarrow{{A}_{n}}\)
We prove that distinguishing number \(D_{\overrightarrow{{S}_{n}}}(X)\) can be at most \(n+1+[\frac{n}{6}]\) for \(n\le 36\) and find the complete sets of distinguishing numbers \(D_{\overrightarrow{{S}_{2}}}(X)\) and \( D_{\overrightarrow{{A}_{2}}}(X)\)
- PDF / 163,385 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 49 Downloads / 176 Views
can be at most n + 1 + [ n ] Abstract We prove that distinguishing number D− 6 Sn → (X ) and D− → (X ). for n ≤ 36 and find the complete sets of distinguishing numbers D− S2 A2 − → − → The distinguishing numbers of the actions of S3 and A3 are also discussed.
Keywords Distinguishing number · Distinguishing group actions · Labeling of sets and graphs
1 Introduction − → The wreath product Sn is defined as n
Definition 1.1 Let Z2 = { f | f : {1, 2, . . . , n} −→ Z2 }. Define − → Sn = Z2 Sn = {( f, π ) | f : {1, 2, . . . , n} −→ Z2 , π ∈ Sn }, − → where Sn is the symmetric group on n symbols. Sn is a group under the composition defined by ( f, π )( f , π ) = ( f f π−1 , π π ), where ( f f )(i) = f (i) + f (i), i ∈ {1, 2, . . . , n} and f π−1 = f ◦ π , for π ∈ Sn n and f ∈ Z2 . This group of type Bn is called the wreath product of Z2 by Sn . − → The group Sn has a presentation with generators S = {s1 , s2 , . . . , sn }, satisfying s 2 = 1, for every i ≥ 1 i 2 si s j = 1 if |i − j| = 1 (si si+1 )3 = 1 for every i ≥ 2, and (s1 s2 )4 = 1. − → This group Sn is isomorphic to the group of signed Brauer diagrams having no horizontal edges. For more detail about Brauer and signed Brauer algebras one can refer to [4, 5, 7–9, 11].
(1) (2) (3) (4)
R.P. Sharma (B) · R. Parmar · V.S. Kapil Department of Mathematics, Himachal Pradesh University, Summer Hill, Shimla 171005, India e-mail: [email protected] © Springer Science+Business Media Singapore 2016 S.T. Rizvi et al. (eds.), Algebra and its Applications, Springer Proceedings in Mathematics & Statistics 174, DOI 10.1007/978-981-10-1651-6_20
329
330
R.P. Sharma et al.
− → Since the subgroup of Sn that is generated by si , i = 2, 3, . . . , n is isomorphic − → to Sn , this subgroup of Sn is identified with Sn by taking each si , i ≥ 2 to the basic transposition (i − 1, i). − → The group Sn becomes a subgroup of S2n as observed in [3] − → Definition 1.2 For any integer n ≥ 2, the group Sn can be identified to be the subgroup of S2n as follows: − → Sn = {θ ∈ S2n |θ (i) + θ (−i) = 0, for all i, 1 ≤ i ≤ n}. Here, the set {1, 2, 3, . . . , n, n + 1, . . . , 2n} is identified by {1, 2, . . . , n, −1, −2, . . . − n}. In this paper, we use the former notation. In [6], the authors found − → the elements of Sn which correspond to even permutations in S2n . The set of such − → − → elements form a normal subgroup of Sn of order 2n−1 n! denoted by An . We are interested to find the distinguishing numbers of the actions of these groups on various sets. ˆ φ : V (G) ˆ −→ {1, 2, 3, . . . , r } is said to be A labeling of the vertices of a graph G, r -distinguishing provided no automorphism of the graph preserves all of the vertex ˆ there exists x in V = V (G) ˆ such that labels. That is, for every nontrivial σ ∈ Aut(G) ˆ denoted by D(G), ˆ is the φ(x) = φ(σ (x)). The distinguishing number of a graph G, minimum r such that Gˆ has an r -distinguishing labeling. That is, ˆ = min{r |Gˆ has a labeling that is r-distinguishing (See [1, 2]). D(G) The main algebraic differ
Data Loading...
