On Pairwise Compatibility Graphs

Abstract

This thesis deals with pairwise compatibility graphs. Let T be an edge weighted tree, let dT (u, v) be the sum of the weights of the edges on the path from u to v in T, and let dmin and dmax be two non-negative real numbers. Then a pairwise compatibility graph of T for dmin and dmax is a graph G = (V,E), where each vertex u ∈ V corresponds to a leaf u of T and there is an edge (u , v ) ∈ E if and only if dmin ≤ dT (u, v) ≤ dmax. A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two nonnegative real numbers dmin and dmax such that G is a pairwise compatibility graph of T for dmin and dmax. Pairwise compatibility graph is descended from phylogenetic tree which expresses the evolutionary relationships among different species. Pairwise compatibility graph is not only important for phylogeny applications, but has also given rise to a number of interesting theoretical problems. Unfortunately, however, very few significant results regarding this problem are known to date. Complete characterization of this graph class is not known. It has not been possible yet to give an algorithm for recognizing whether a given graph is pairwise compatibility graph or not. Moreover, the computational complexity of recognizing pairwise compatibility graphs is still unknown. This thesis addresses different important and challenging theoretical problems regarding pairwise compatibility graphs. We deal with the open question regarding whether or not all graphs are pairwise compatibility graphs and settle the corresponding conjecture, which states that every graph is a pairwise compatibility graph, in negative. We also recognize several well known large graph classes as pairwise compatibility graphs. We introduce the new notion of improper PCG, and show that every graph is an improper PCG. In addition, we also present an efficient heuristic algorithm to construct an improper pairwise compatibility tree of any triangulated plane graph.