Hamiltonian cycles in unitary prefix transposition rearrangement graphs

Autor:	Luis Antonio Brasil Kowada, C.S. Reis, A. C. Ribeiro, Celina M. H. de Figueiredo, Letícia Rodrigues Bueno
Rok vydání:	2015
Předmět:	Discrete mathematics Cayley graph Applied Mathematics Unitary state Hamiltonian path Combinatorics Vertex-transitive graph Permutation symbols.namesake Symmetric group symbols Discrete Mathematics and Combinatorics Lovász conjecture Distance Mathematics
Zdroj:	Discrete Applied Mathematics. 192:82-86
ISSN:	0166-218X
DOI:	10.1016/j.dam.2014.05.003
Popis:	Cayley graphs have been extensively studied by graph and group theorists, computer scientists, molecular biologists and coding theorists. We focus on two challenging problems on Cayley graphs arising on sequence comparison: hamiltonian cycle and graph diameter. A unitary prefix transposition exchanges two adjacent blocks in a permutation such that one block contains the first elements and one of the blocks is unitary. The Unitary Prefix Transposition Rearrangement Graph has the permutations in the Symmetric Group S n as its vertex set and two vertices are adjacent if there exists a unitary prefix transposition that applied to a permutation produces the other one. We show that this Cayley graph has diameter n - 1 and is hamiltonian.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::16d2bd602955bd05c578f5527634007b https://doi.org/10.1016/j.dam.2014.05.003 Zobrazit plný text záznamu Full Text from ScienceDirect