id: 05344685
dt: a
an: 05344685
au: Brandstädt, Andreas; Wagner, Peter
ti: On $(k,\ell )$-leaf powers.
so: Kučera, Luděk (ed.) et al., Mathematical foundations of computer science
    2007. 32nd international symposium, MFCS 2007, Český Krumlov, Czech
    Republic, August 26‒31, 2007. Proceedings. Berlin: Springer (ISBN
    978-3-540-74455-9/pbk). Lecture Notes in Computer Science 4708, 525-535
    (2007).
py: 2007
pu: Berlin: Springer
la: EN
cc: 
ut: ($k, \ell$)-leaf powers; leaf powers; leaf roots; strictly chordal graphs;
    linear time algorithms
ci: 
li: doi:10.1007/978-3-540-74456-6_47
ab: Summary: We say that, for $k \geq 2$ and $\ell > k$, a tree $T$ is a
    $(k,\ell )$-leaf root of a graph $G = (V _{G },E _{G })$ if $V _{G }$
    is the set of leaves of $T$, for all edges $xy \in E _{G }$, the
    distance $d _{T }(x,y)$ in $T$ is at most $k$ and, for all non-edges
    $xy \not\in E_G, d _{T }(x,y)$ is at least $\ell $. A graph $G$ is a
    $(k,\ell )$-leaf power if it has a $(k,\ell )$-leaf root. This new
    notion modifies the concept of $k$-leaf power which was introduced and
    studied by Nishimura, Ragde and Thilikos motivated by the search for
    underlying phylogenetic trees. Recently, a lot of work has been done on
    $k$-leaf powers and roots as well as on their variants phylogenetic
    roots and Steiner roots. For $k = 3$ and $k = 4$, structural
    characterisations and linear time recognition algorithms of $k$-leaf
    powers are known, and, recently, a polynomial time recognition of
    5-leaf powers was given. For larger $k$, the recognition problem is
    open. We give structural characterisations of $(k,\ell )$-leaf powers,
    for some $k$ and $\ell $, which also imply an efficient recognition of
    these classes, and in this way we also improve and extend a recent
    paper by Kennedy, Lin and Yan on strictly chordal graphs and leaf
    powers.
rv: