Uniquely pressable graphs: characterization, enumeration, and recognition

DOI10.1016/j.aam.2018.09.005zbMath1402.05098arXiv1706.07468OpenAlexW2963709356WikidataQ129030674 ScholiaQ129030674MaRDI QIDQ1755655

Hays Whitlatch, Joshua N. Cooper

Publication date: 10 January 2019

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitygraph theoryCholesky factorizationadjacency matrixbinary matrixphylogeneticspressing sequencegenome reversals

Mathematics Subject Classification ID

Factorization of matrices (15A23) Graph theory (including graph drawing) in computer science (68R10) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Enumeration in graph theory (05C30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Protein sequences, DNA sequences (92D20) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (1)

A new characterization of \(\mathcal{V} \)-posets

Cites Work

• On average and highest number of flips in pancake sorting
• An \((18/11)n\) upper bound for sorting by prefix reversals
• Successful pressing sequences for a bicolored graph and binary matrices
• Proving the pressing game conjecture on linear graphs
• Counting linear extensions
• A note on the graph isomorphism counting problem
• Bounds for sorting by prefix reversal
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• On the average number of reversals needed to sort signed permutations
• The distribution of cycles in breakpoint graphs of signed permutations
• On the complexity of matrix reduction over finite fields
• Fast matrix decomposition in \(\mathbb F_2\)
• Transforming cabbage into turnip
• The Complexity of Enumeration and Reliability Problems
• Sorting by Transpositions
• Graph isomorphism in quasipolynomial time [extended abstract]
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Uniquely pressable graphs: characterization, enumeration, and recognition