Exact leaf powers

DOI10.1016/j.tcs.2010.04.027zbMath1193.05141MaRDI QIDQ982668

Dieter Rautenbach, Andreas Brandstädt, Van Bang Le

Publication date: 7 July 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.04.027

zbMATH Keywords

phylogeny; phylogenetic tree; forbidden induced subgraph; graph power; leaf power; leaf root

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C12: Distance in graphs

05C76: Graph operations (line graphs, products, etc.)

Related Items

Simplicial Powers of Graphs, On k- Versus (k + 1)-Leaf Powers, Inferring phylogenetic trees from the knowledge of rare evolutionary events, Exact-2-relation graphs, On graphs that are not PCGs, Pairwise Compatibility Graphs: A Survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tolerance graphs
• Structure and linear time recognition of 3-leaf powers
• Characterizations of strongly chordal graphs
• Modular decomposition and transitive orientation
• Computing roots of graphs is hard
• NeST graphs
• Neighborhood subtree tolerance graphs
• A characterisation of rigid circuit graphs
• Some remarks about leaf roots
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• On Graph Powers for Leaf-Labeled Trees
• A Class of Balanced Matrices Arising from Location Problems
• Locality in Distributed Graph Algorithms
• Tree Powers
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Algorithms for Square Roots of Graphs
• Structure and linear-time recognition of 4-leaf powers
• Four Characters Suffice to Convexly Define a Phylogenetic Tree
• Depth-First Search and Linear Graph Algorithms
• Algorithms and Computation