The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

PLG

Seminar

On k-leaf powers

Brandstaedt, A (Rostock)
Tuesday 04 September 2007, 12:10-12:30

Seminar Room 1, Newton Institute

Abstract

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.

Presentation

[ppt ]

Audio

MP3MP3

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧