Source author record

Annachiara Korchmaros

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.GR

Catalog footprint

Research overview

5works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Circles and Paths in 2-Colored Best Match Graphs

Recent investigations in computational biology focus on a family of 2-colored digraphs, called 2-colored best match graphs, which naturally arise from rooted phylogenetic trees. Actually the defining properties of such graphs are unexpectedly unusual in graph theory, and they were established only recently after the discovery of their links to evolutionary relatedness via phylogenetic trees. In this paper several results are obtained on 2-colored best match graphs which well fit in the mainstream of graph theory.

preprint2015arXiv

Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

This paper deals with the Cayley graph $\mathrm{Cay}(\mathrm{Sym}_n,T_n),$ where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that Aut $(\mathrm{Cay}(\mathrm{Sym}_n,T_n))$ is the product of the left translation group by a dihedral group $\mathsf{D}_{n+1}$ of order $2(n+1)$ . The proof uses several properties of the subgraph $Γ$ of $\mathrm{Cay}(\mathrm{Sym}_n,T_n)$ induced by the set $T_n$ . In particular, $Γ$ is a $2(n-2)$ -regular graph whose automorphism group is $\mathsf{D}_{n+1},$ $Γ$ has as many as $n+1$ maximal cliques of size $2,$ and its subgraph $Γ(V)$ whose vertices are those in these cliques is a $3$ -regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of $\mathsf{D}_{n+1}$ of order $n+1$ with regular Cayley maps on $\mathrm{Sym}_n$ is also discussed. It is shown that the product of the left translation group by the latter group can be obtained as the automorphism group of a non- $t$ -balanced regular Cayley map on $\mathrm{Sym}_n$ .

preprint2015arXiv

Cayley graph on symmetric groups with generating block transposition sets

This paper deals with the Cayley graph $\Cay,$ where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. We prove that ${\rm{Aut}}(\Cay)$ is the product of the right translation group by $\textsf{N}\rtimes \textsf{D}_{n+1},$ where $\textsf{N}$ is the subgroup fixing $S_n$ element-wise and $\textsf{D}_{n+1}$ is a dihedral group of order $2(n+1)$ . We conjecture that $\textsf{N}$ is trivial. We also prove that the subgraph $Γ$ with vertex-set $S_n$ is a $2(n-2)$ -regular graph whose automorphism group is $\textsf{D}_{n+1}$ . Furthermore, $Γ$ has as many as $n+1$ maximum cliques of size $2.$ Also, its subgraph $Γ(V)$ whose vertices are those in these cliques is a $3$ -regular, Hamiltonian, and vertex-transitive graph.

preprint2015arXiv

Combinatorial properties of block transpositions on Symmetric groups

A major problem in the study of combinatorial aspects of permutation groups is to determine the distances in the symmetric group $\Sym_n$ with respect to a generator set. One well-known such a case is when the generator set $S_n$ consists of block transpositions. It should be noted that "the block transposition distance of a permutation" is the distance of the permutation from the identity permutation in the Cayley graph $\Cay$, and "sorting a permutation by block transpositions" is equivalent to finding shortest paths in $\Cay$. The original results in our thesis concern the lower and upper bounds on the block transpositions diameter of $\Sym_n$ with respect to $S_n$ and the automorphism group $\Aut(\Cay)$. A significant contribution is to show how from the toric equivalence can be obtained bijective maps on $\Sym_n$ that we call \emph{toric maps}. Using the properties of the toric maps, we discuss the role of the invariance principle of the block transposition distance within toric classes in the proof of the Eriksson bound. Furthermore, we prove that $\Aut(\Cay)$ is the product of the right translation group by $\textsf{N}\rtimes\textsf{D}_{n+1}$ , where $\textsf{N}$ is the subgroup fixing $S_n$ elementwise, and $\textsf{D}_{n+1}$ is a dihedral group whose maximal cyclic subgroup is generated by the toric maps. Computer aided computation supports our conjecture that $\textsf{N}$ is trivial. Also, we prove that the subgraph $Γ$ with vertex-set $S_n$ is a $2(n-2)$ -regular graph whose automorphism group is $\textsf{D}_{n+1}$ . We show some aspects of $\Cay$, notably $Γ$ has as many as $n+1$ maximal cliques of size $2$ , its subgraph $Γ(V)$ whose vertices are those in these cliques is a $3$ -regular Hamiltonian graph, and $\textsf{D}_{n+1}$ acts faithfully on $V$ as a vertex regular automorphism group.

preprint2014arXiv

Upper bound on the block transposition diameter of the symmetric group

Given a generator set $S$ of the symmetric group ${\rm{Sym}}_n$ , every permutation $π\in {\rm{Sym}_n}$ is a word (product of elements) of $S$ . A positive integer $d(π)$ is associated with each $π\in{\rm{Sym}_n}$ taking the length of the shortest such word, and the $S$ -diameter $d(S)$ is the maximum value of $d(π)$ with $π$ ranging over ${\rm{Sym_n}}$ . The distance $d(π,ν)$ of two permutations $π,ν$ defined by $d(ν^{-1}\circπ)$ satisfies the axioms of a metric space. In this paper we consider the case where $S$ consists of all block transpositions of ${\rm{Sym_n}}$ and call $d(π)$ the block transposition distance of $π$ . A strong motivation for the study of this special case comes from investigations of large-scale mutations of genome, where determining $d(π)$ is known as sorting the permutation $π$ by block transpositions. In the papers on this subject, toric equivalence classes often play a crucial role since $d(π)=d(ν)$ when $π$ and $ν$ are torically equivalent. A proof of this result can be found in the (unpublished) Hausen's Ph.D Dissertation thesis; see \cite{Ha}. Our main contribution is to obtain a bijective map on ${\rm{Sym}_n}$ from the toric equivalence that leaves the distances invariant. Using the properties of this map, we give an alternative proof of Hausen's result which actually fills a gap in the proof of the upper bound on $d(S)$ due to Eriksson and his coworkers; see \cite{EE}. We also revisit the proof of the key lemma \cite[Lemma 5,1]{EE}, giving more details and filling some gaps.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Annachiara Korchmaros

Research overview

Is this your work?

5 publications

Circles and Paths in 2-Colored Best Match Graphs

Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

Cayley graph on symmetric groups with generating block transposition sets

Combinatorial properties of block transpositions on Symmetric groups

Upper bound on the block transposition diameter of the symmetric group

See the researcher in context

Building this map preview