Bijection and Isomorphism on Graph of Sn (123,132) from One of (n-1) Length Binary Strings

Juarna, Asep and Mutiara, A.B Bijection and Isomorphism on Graph of Sn (123,132) from One of (n-1) Length Binary Strings. International Journal of Computer Science and Information Security, 9 (4).

[img]
Preview
Text
Bijection and Isomorphism on Graph of Sn (123,132) from One of (n-1) Length Binary Strings_UG.pdf - Submitted Version

Download (7Mb) | Preview

Abstract

Simion and Sdunidt showed in 1985 that the dinaIity 01' the set S,,(I23,132llength 11permutations avoidmg patterns 123 and 132, is r- , but in the other side r-1 is the dinality of the set B. 1 = {O,I}·1 orIength (11-1) binary strinp. eoretically, it must exist a bijection between S,,(I23,132) and I. In thls paper we give a COIL'Jtructive bijection between B.1 18,,(123,132); we show that it is actually an isomorphism and strate this by constructing a Gray code for S,,(I23,132) from a own similar result for B .. 1 As we noted that an isomorphism t'cen two combinatorial classes is a closeness preserving fctionbetween those classes, that is, two objects in a class are ~ if and only if their baaces by this bijection are also closed. en, as in this paper, doseness is expressed in terms of nming distance. Isomorphism allows us to find out some perties of a corn binatorial class X (or for the graph induced by class Xl if those properties are found in the pre image of the ,bmatorial class X; some mentioned properties are ,iltonian path, graph diameter, eIhaustive and random eration, and ranking and Wlranking algorithms.

Item Type: Article
Uncontrolled Keywords: hamming distance; binary strings
Subjects: A General Works > AI Indexes (General)
Divisions: Fakultas Ilmu Komputer dan Teknologi Informasi > Program Studi Sistem Informasi
Depositing User: Mr Reza Chandra
Date Deposited: 25 Feb 2014 00:56
Last Modified: 25 Feb 2014 00:56
URI: http://repository.gunadarma.ac.id/id/eprint/15

Actions (login required)

View Item View Item