Back to Search
Start Over
Uniquely pressable graphs: Characterization, enumeration, and recognition.
- Source :
-
Advances in Applied Mathematics . Feb2019, Vol. 103, p13-42. 30p. - Publication Year :
- 2019
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPHIC methods
*GRAPH theory
*ALGORITHMS
*MATHEMATICAL models
*NUMERICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 01968858
- Volume :
- 103
- Database :
- Academic Search Index
- Journal :
- Advances in Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 133169050
- Full Text :
- https://doi.org/10.1016/j.aam.2018.09.005