2010/12/18 by Michel Habib, Habib, Michel, Thu‐Hien To +2
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Computer Science · #Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #Plant Reproductive Biology #Plant and Fungal Species Descriptions #Plant and animal studies #Quantitative Methods (q-bio.QM) #cs.DM #q-bio.QM
paper · pdf · doi:10.48550/arxiv.1012.4084
openalex publication_date 2010/12/18 · arxiv created 2011/07/23 · arxiv updated 2015/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is a k-leaf power of a tree T if its vertices are leaves of T and two vertices are adjacent in T if and only if their distance in T is at most k. Then T is a k-leaf root of G. This notion was introduced by Nishimura, Ragde, and Thilikos [2002] motivated by the search for underlying phylogenetic trees. We study here an extension of the k-leaf power graph recognition problem. This extension is motivated by a new biological question for the evaluation of the latteral gene transfer on a population of viruses. We allow the host graph to slightly differs from a tree and allow some cycles. In fact we study phylogenetic galled networks in which cycles are pairwise vertex disjoint. We show some structural results and propose polynomial algorithms for the cases k=3 and k=4. As a consequence, squares of galled networks can also be recognized in polynomial time.