A survey on pairwise compatibility graphs. Issue 3 (1st September 2020)

• Record Type: Journal Article
• Authors: Rahman, Md. Saidur; Ahmed, Shareef
• Is Part Of: AKCE International Journal of Graphs and Combinatorics. Volume 17:Issue 3(2020)
• Page Start: 788
• Page End: 795
• Publication Date: 2020-09-01
• Subjects: Pairwise compatibility graphs -- phylogenetic trees -- leaf power graphs -- multi-interval pairwise compatibility graphs
• DOI: 10.1016/j.akcej.2019.12.011
• Languages: English
• ISSNs: 0972-8600

Abstract

Abstract: Let T be an edge weighted tree and dmin, dmax be two non-negative real numbers where d min ≤ d max . The pairwise compatibility graph (PCG) of T for dmin, dmax is a graph G such that each vertex of G corresponds to a distinct leaf of T and two vertices are adjacent in G if and only if the weighted distance between their corresponding leaves lies within the interval [ d min, d max ] . A graph G is a PCG if there exist an edge weighted tree T and suitable dmin, dmax such that G is a PCG of T . The class of pairwise compatibility graphs was introduced to model evolutionary relationships among a set of species. Since not all graphs are PCGs, researchers become interested in recognizing and characterizing PCGs. In this paper, we review the results regarding PCGs and some of its variants.