On strongly chordal graphs that are not leaf powers

DOI10.1007/978-3-319-68705-6_29MaRDI QIDQ1687937zbMATH OpenOpenAlexFDO

Authors Manuel Lafond

Publication date 4 January 2018

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

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: A common task in phylogenetics is to find an evolutionary tree representing proximity relationships between species. This motivates the notion of leaf powers: a graph G = (V, E) is a leaf power if there exist a tree T on leafset V and a threshold k such that uv is an edge if and only if the distance between u and v in T is at most k. Characterizing leaf powers is a challenging open problem, along with determining the complexity of their recognition. This is in part due to the fact that few graphs are known to not be leaf powers, as such graphs are difficult to construct. Recently, Nevries and Rosenke asked if leaf powers could be characterized by strong chordality and a finite set of forbidden subgraphs. In this paper, we provide a negative answer to this question, by exhibiting an infinite family G of (minimal) strongly chordal graphs that are not leaf powers. During the process, we establish a connection between leaf powers, alternating cycles and quartet compatibility. We also show that deciding if a chordal graph is G-free is NP-complete, which may provide insight on the complexity of the leaf power recognition problem.

Recommendations

• Strictly chordal graphs are leaf powers
• scientific article; zbMATH DE number 4077265
• A characterization of strongly chordal graphs
• A new characterization of strongly chordal graphs
• scientific article; zbMATH DE number 165077
• On strictly chordality-\(k\) graphs
• On powers of chordal graphs and their colorings
• Strong chromatic index of chordless graphs
• Strengthening strongly chordal graphs
• Dually and strongly chordal graphs

Cited in

(8)

• Mim-width. III. Graph powers and generalized distance domination problems
• scientific article; zbMATH DE number 4077265 (Why is no real title available?)
• Recognition of linear and star variants of leaf powers is in P
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• Boxicity of leaf powers
• Lower bounds for leaf rank of leaf powers
• k-leaf powers cannot be characterized by a finite set of forbidden induced subgraphs for k 5
• Strictly chordal graphs are leaf powers

This page was built for publication: On strongly chordal graphs that are not leaf powers

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