On Graphs that are not PCGsI

Let T be an edge-weighted tree and let dmin; dmax be two nonnegative real numbers. The pairwise compatibility graph (PCG) of T is a graph G such that each vertex of G corresponds to a distinct leaf of T and two vertices are adjacent inG if and only if the weighted distance between their corresponding leaves in T is in the interval [dmin; dmax]. Similarly, a given graph G is a PCG if there exist suitable T; dmin; dmax, such that G is a PCG of T. Yanhaona, Bayzid and Rahman proved that there exists a graph with 15 vertices that is not a PCG. On the other hand, Calamoneri, Frascaria and Sinaimeri proved that every graph with at most seven vertices is a PCG. In this paper we IA preliminary version of these results appeared in the Proceedings of the 7th Interna-tional Workshop on Algorithms and Computation (WALCOM 2013) [9]