Graphs we deal with in this paper are motivated by a fundamental
problem in computational biology, that is the reconstruction of
phylogenetic trees, i.e. trees where leaves represent known taxa while
internal nodes possible ancestors that might have led through
evolution to this set of taxa [
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 2 V is
uniquely associated to a leaf of T and there is an edge (u; v) 2 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 .
In such a case, we say that G is a PCG of T for dmin and dmax; in
symbols, G = P CG(T; dmin; dmax) [
u a u c b u u d
In Figure 1.a a small graph that is P CG(T; 4; 5) is depicted and,
in Figure 1.b, T is shown. In general, T is not unique; here T is a
caterpillar, i.e. a tree consisting of a central path to which all the
other nodes are directly connected. Due to their simple structure,
caterpillars are the most used witness trees to show that a graph is
PCG. However, it has been proven that there are some PCGs for
which it is not possible to nd a caterpillar as witness tree [
Due to the exibility a orded in the construction of instances (i.e.
choice of tree topology and values for dmin and dmax), when PCGs
were introduced, it was also conjectured that all graphs are PCGs [
It remains unclear which is the boundary between PCGs and not PCGs, so we focus on searching new graph classes that are not PCGs.
u u u u u u u u u u u u u u u u
u u u u
Namely, we consider three classes of n-node graphs, n are all modi cations of cycles: { graphs obtained as strong product between an n=2 cycle and K2; { graphs obtained as the square of an n cycle; { graphs obtained connecting the nodes of an (n 1) cycle with an universal node (wheels).
We study the rst class because naturally extends the graph in
Figure 2.b, that can be interpreted as C4 K2. The graphs in the
second class are a natural variation of cycles, that have been proved
to be PCGs [
In the following section we communicate all our results concerning these three classes in relation to the pairwise compatibility property. All the proofs are detailed in the extended version of this paper. 2
Given two graphs G and H, their strong product G H is a graph whose node set is the cartesian product of the node sets of the two graphs, and there is an edge between nodes (u; v) and (u0; v0) if and c u u uv1 only if either u = u0 and (v; v0) is an edge of H or v = v0 and (u; u0) is an edge of G or both (u; u0) and (v; v0) are edges in G and H respectively.
We highlight that when k = 4, Ck K2 is the graph in Figure 2.b and it is known not to be PCG. In the extended version of this paper we present an ad-hoc proof for k = 5 and a general proof for k 6.
Given a graph G, its square graph G2 is a graph whose node set coincides with the node set of G and there is an edge (u; v) in G2 if and only if either u and v are adjacent or they are connected by a 2 length path in G.
Also in this case, we prove separately the cases n = 8; 9 from the general case n 10.
Let Wn be the wheel obtained by connecting all the nodes of an (n 1) cycle Cn 1 with a central (universal) node.
It is known that W7 is PCG (see a witness tree in Figure 3.a). In Figure 3.b we show a witness tree for W8, so proving the following theorem:
On the contrary, when n 8, we prove that wheels are not PCGs:
Our last results concern minimality of the previously de ned classes of graphs, where a not PCG is minimal if, by deleting any node from it, we get a PCG.
from Ck
from C2 is PCG. In other words, C2 is a minimal not PCG.
from Wn is PCG. In other words, Wn is a minimal not PCG.
This work has been partially supported by Sapienza University of Rome projects \Graph Algorithms for Phylogeny: a promising approach" and \Combinatorial structures and algorithms for problems in co-phylogeny".