Ricerc@Sapienza

A graph G = (V,E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dminand dmax, dmin≤ dmax, such that each node u∈V is uniquely associated to a leaf of T and there is an edge (u, v) ∈ E if and only if dmin≤ dT(u, v) ≤ dmax, where dT(u, v) is the sum of the weights of the edges on the unique path PT(u, v) from u to v in T. Understanding which graph classes lie inside and which ones outside the PCG class is an important issue. Despite numerous efforts, a complete characterization of the PCG class is not known yet.

A graph G=(V,E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax, dmin≤dmax, such that each node u∈V is uniquely associated to a leaf of T and there is an edge (u,v)∈E if and only if dmin≤dT(u,v)≤dmax, where dT(u,v) is the sum of the weights of the edges on the unique path PT(u,v) from u to v in T. Understanding which graph classes lie inside and which ones outside the PCG class is an important issue.