A survey on pairwise compatibility graphs

Abstract

Let T be an edge weighted tree and dmin, dmax be two non-negative real numbers where 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 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.

Keywords

• pairwise compatibility graphs
• phylogenetic trees
• leaf power graphs
• multi-interval pairwise compatibility graphs