The Sortability of Graphs and Matrices under Context Directed Swaps
From MaRDI portal
Publication:6316769
arXiv1904.03287MaRDI QIDQ6316769FDOQ6316769
Authors: Christopher A. Brown, C. S. Carrillo Vazquez, Rohit Goswami, Simon Heil, Marion Scheepers 
Publication date: 5 April 2019
Abstract: The study of sorting permutations by block interchanges has recently been stimulated by a phenomenon observed in the genome maintenance of certain ciliate species. The result was the identification of a block interchange operation that applies only under certain constraints. Interestingly, this constrained block interchange operation can be generalized naturally to simple graphs and to an operation on square matrices. This more general context provides numerous techniques applicable to the original context. In this paper we consider the more general context, and obtain an enumeration, in closed form, of all simple graphs on n vertices that are ``sortable" by the graph analogue of the constrained version of block interchanges. We also obtain asymptotic results on the proportion of graphs on n vertices that are so sortable.
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Exact enumeration problems, generating functions (05A15) Searching and sorting (68P10) Eulerian and Hamiltonian graphs (05C45)
This page was built for publication: The Sortability of Graphs and Matrices under Context Directed Swaps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6316769)
