solidot新版网站常见问题,请点击这里查看。

Uniquely Pressable Graphs: Characterization, Enumeration, and Recognition. (arXiv:1706.07468v1 [math.CO])

来源于:arXiv
We consider "pressing sequences", a certain kind of transformation of graphs with loops into empty graphs, motivated by an application in phylogenetics. In particular, we address the question of when a graph has precisely one such pressing sequence, thus answering an question from Cooper and Davis (2015). We characterize uniquely pressable graphs, count the number of them on a given number of vertices, and provide a polynomial time recognition algorithm. We conclude with a few open questions. Keywords: Pressing sequence, adjacency matrix, Cholesky factorization, binary matrix 查看全文>>