Uniquely Pressable Graphs: Characterization, Enumeration, and Recognition

Abstract Motivated by the study of genomes evolving by reversals, we consider pseudograph transformations known as “pressing sequences”. In particular, we address the question of when a graph has precisely one pressing sequence resulting in the empty graph, thus answering an question from Cooper and Davis (2015) [13] . We characterize such “uniquely pressable” graphs, count the number of them on a given number of vertices, and provide a polynomial-time recognition algorithm. We conclude with several open questions.