On k-leaf powers
Seminar Room 1, Newton Institute
In 2002, Nishimura, Ragde and Thilikos introduced the notion of k-leaf power and k-leaf root, motivated by the following: ``... a fundamental problem in computational biology is the reconstruction of the phylogeny, or evolutionary history, of a set of species or genes, typically represented as a phylogenetic tree ...''. The species occur as leaves of the phylogenetic tree. Let G=(V_G,E_G) be a finite undirected graph. For k at least 2, a tree T is a $k$-leaf root of G if V_G is the leaf set of T and two vertices x,y in V_G are adjacent in G if and only if their distance d_T(x,y) in T is at most k. The graph G is a $k$-leaf power if it has a k-leaf root. Obviously, a graph is a 2-leaf power if and only if it is the disjoint union of cliques, i.e., it contains no induced path of three vertices. Recent work on leaf powers contains characterisations of 3- and 4-leaf powers and their variants. It is well known that every k-leaf power is a strongly chordal graph. For k at least 6, no characterisation of $k$-leaf powers and no efficient recognition is known. We discuss some open problems and new results on leaf powers.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.