Successful pressing sequences for a bicolored graph and binary matrices

DOI10.1016/J.LAA.2015.11.001zbMATH Open1331.05140OpenAlexW2963633439MaRDI QIDQ898795FDOQ898795

Authors N. E. Zubov

Publication date 18 December 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.07450

zbMATH Keywords

matchingadjacency matrixbinary matrixpressing sequencebicolored graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Problems related to evolution (92D15) Matrices over special rings (quaternions, finite fields, etc.) (15B33)

Abstract: We apply matrix theory over $mathbb{F}_2$ to understand the nature of so-called "successful pressing sequences" of black-and-white vertex-colored graphs. These sequences arise in computational phylogenetics, where, by a celebrated result of Hannenhalli and Pevzner, the space of sortings-by-reversal of a signed permutation can be described by pressing sequences. In particular, we offer several alternative linear-algebraic and graph-theoretic characterizations of successful pressing sequences, describe the relation between such sequences, and provide bounds on the number of them. We also offer several open problems that arose as a result of the present work.

Recommendations

• Proving the pressing game conjecture on linear graphs
• Uniquely pressable graphs: characterization, enumeration, and recognition
• On the consecutive ones property
• Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theorem
• Leaf Pairs and Tree Dissections

Cites work

• scientific article; zbMATH DE number 6472609 (Why is no real title available?)
• A very elementary presentation of the Hannenhalli-Pevzner theory
• Transforming cabbage into turnip

Cited in

(5)

• A new characterization of \(\mathcal{V} \)-posets
• Proving the pressing game conjecture on linear graphs
• Uniquely pressable graphs: characterization, enumeration, and recognition
• Sorting by reversals and the theory of 4-regular graphs
• Complexity and enumeration in models of genome rearrangement

This page was built for publication: Successful pressing sequences for a bicolored graph and binary matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898795)