Successful pressing sequences for a bicolored graph and binary matrices

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

Authors: N. E. Zubov 

Publication date: 18 December 2015

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Transforming cabbage into turnip
• A very elementary presentation of the Hannenhalli-Pevzner theory

Cited In (5)

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

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)