solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看238次
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 查看全文>>