Abstract
A graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k, then we call the graph a k-interval-PCG; in symbols, G = k-interval-PCG (T, I1,…, Ik).
It is known that 2-interval-PCGs do not contain all graphs, and the smallest known graph outside this class has 135 nodes. Here, we prove that all graphs with at most 8 nodes are 2-interval-PCGs, so doing one step towards the determination of the smallest value of n such that there exists an n node graph that is not a 2-interval-PCG.
Introduction
A graph G = (V, E) is a pairwise compatibility graph (PCG) if there exist an edge-weighted tree T with non-negative real values and an interval I of the non-negative real half-line 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
The concept of pairwise compatibility was introduced in [10] in a computational biology context and it was conjectured that every graph is a PCG. The conjecture has then been confuted in [15], where the first examples of graphs that are not PCGs were provided. Since then, much work has been done in order to understand which graphs are PCGs (e.g. see the surveys [8, 14]).
Knowing that not all graphs are PCGs, a natural generalization of PCGs has been introduced in [1]: a graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k, then we call the graph a k-interval-PCG; in symbols, G = k-interval-PCG (T, I1,…,Ik).
When k = 1, the 1-interval-PCG class coincides with the PCG class. Instead, already when k = 2 the graph class of PCGs is strictly contained in the graph class of 2-interval-PCGs; indeed, there exist graphs that are not PCGs but are 2-interval-PCGs: the smallest such graph has 8 nodes [9]; other graphs that are not in PCG but are in 2-interval-PCG are wheels (i.e., one universal node connected to all the nodes of a cycle) with at least 9 nodes and a restricted subclass of series-parallel graphs [1].
It is also known that 2-interval-PCGs do not contain all graphs and the smallest known graph outside this class has 135 nodes [7]; moreover, it is known that some classes of graphs, such as grid graphs, are in 2-interval-PCG, whatever their size [12]. A natural question is which is the smallest value of n such that there exists an n-node graph that is not a 2-interval-PCG. In this paper, we take one step in this direction: it is known that all graphs with at most 7 nodes are PCGs [5] and hence 2-interval-PCGs; here we show that all graphs with 8 nodes are 2-interval-PCGs, and to do it, it is enough to focus on the 8-node graphs that are not PCGs. Note that we are working analogously as for PCGs. Indeed, the first graph recognized to be outside the PCG class had 15 nodes [15]; in order to find the smallest graph not in PCG, Phillips [13] first proved in an exhaustive way that all graphs with less than five nodes are PCGs, then the result was extended to all graphs with at most seven nodes [5] and later to all bipartite graphs on eight nodes [11]. Finally, Durocher, Mondal, and Rahman [9] proved that there exists a graph with 8 nodes that is not a PCG.
There exist only seven graphs G1,…, G7 with 8 nodes that are not PCGs [2] and are depicted in Figure 1. Only G1 is already known to be in 2-interval-PCG [7]; here we prove that all the others are 2-interval-PCGs as well. In fact, our result is summarized in Figure 2, and the rest of the paper is needed to justify this figure. More in detail, this paper is organized as follows: in Section 2 we prove some general results giving sufficient conditions for a graph to be in (k + 1)-interval-PCG if certain subgraphs are in k-interval-PCG, and we exploit them to prove that G4, G6 and G7 are 2-interval-PCGs; in Section 3 we generalize some results proved for PCGs to let them work for 2-interval-PCGs, too, and we exploit an ILP model to determine whether a given graph is a 2-interval-PCG with respect to a given tree structure; from it, we deduce that the remaining 8-node graphs are 2-interval-PCGs. Finally, we are able to find witness trees and intervals for all the graphs in Figure 1; we show them in Figures 2 and 3, observing that they have all the same structure (either complete binary tree or caterpillar). Section 4 concludes the paper.
The seven graphs with 8 nodes that are not PCGs.
The seven witness complete binary trees with 8 leaves and the corresponding intervals.
The seven witness caterpillars with 8 leaves and the corresponding intervals.
To show that graphs G4, G6 and G7 of Figure 1 are 2-interval-PCGs, we prove two theorems giving sufficient conditions for a graph to be a 2-interval-PCG.
Let G be a graph, a universal node for G is a node that is adjacent to all other nodes of G; a node is almost universal for G if it is adjacent to all the nodes in G but one.
We now prove the following general result.
Theorem 2.1.
Let G be a graph with a universal node u. If the subgraph G′ of G, obtained from G by removing u, is a k-interval-PCG, then G is a (k + 1)-interval-PCG.
Let G′ = PC G(T, I1,…,Ik) with Ik = [a, b]. We construct a new tree T1 adding to the tree T a leaf corresponding to u and define a new interval Ik + 1 such that G = PCG(T1, I1,…,Ik, Ik + 1).
Let p be the maximum distance between the leaves of T (note that it is not restrictive to assume that b ≤ p). We construct T1 by adding to T the new leaf corresponding to u as a child of an internal node x of T and edge (x, u) in T1 is assigned a weight p + 1.
First note that leaf u in T1 has a distance at least p + 1 from all the other leaves of T1 and no larger than 2p + 1.
We set Ik + 1 = [p + 1, 2p + 1] and observe that the interval I1,…, Ik and Ik + 1 are disjoint since b < p + 1. It is easy to see that G coincides with (k + 1)-interval-PCG(T1, I1,…,Ik + 1), that is G is in (k + 1)-interval-PCG.
Note that node 4 in graphs G6 and G7 in Figure 1 is a universal node and their subgraphs obtained deleting it has seven vertices and are hence PCGs (see [5]). The next result straightforwardly follows from this observation and from Theorem 2.1:
Corollary 2.2.
Non PCG graphs G6 and G7 are in 2-interval-PCG.
In order to handle graph G4, we prove the following general result.
Theorem 2.3.
Let G be a graph with an almost universal node u. If the subgraph G′ of G, obtained from G by removing u, is an k-interval-PCG, then G is a (k + 1)-interval-PCG.
Let G′ = PCG(T, I1,…,Ik) with Ii = [ai, bi], 1 ≤ i ≤ ≤k. Starting from tree T we now create a new tree T1 by adding a weight 2 to all the edges of T incident to the leaves. In this way, the distances between any two leaves in T are augmented by exactly 4 in T1 and hence G′ = PCG(T1, I′1,…,I′k + 1) where Ii = [ai + 4, bi + 4] and the weight of each edge incident to a leaf is strictly larger than 1.
Let v be the only node not connected with the almost universal node u of G, and let x be the parent of leaf v in T1; call c the weight of edge (v, x) in T1. (Note that c ≥ 2). Now construct a new tree T2 obtained from T1 deleting edge (v, x) and adding a dummy internal node y connected with v and x, where edge (v, y) has weight 1 and edge (y, x) has weight c − 1. Obviously, again G′ = PCG(T2, I′1,…,I′k).
Let p be the maximum distance between the leaves of T2 and hence it is not restrictive to assume that for the right extreme of Ik is bk + 4 ≤ p. Finally construct T3 adding to T2 new leaf u connected to y with an edge of weight p. Note that u has distance p + 1 from v in T3. Moreover, the distance in T3 between u and any other leaf is less than 2p and at least p + 2. Indeed, the weight of edge (u, y) is p and the weight of the unique incident edge of any other leaf is at least 2. So, we set I′k + 1 = [p + 2, 2p].
Easily I′1, … I′ k and Ik + 1 are disjoint and G = (T3, I′1, …, I′k + 1) and hence it is a (k + 1)- interval-PCG.
Node 1 in graph G4 of Figure 1 is an almost universal node, and the subgraph of G4 obtained by deleting this node is a PCG having seven nodes [5]. So, by Theorem 2.3, we have the following result.
Corollary 2.4.
Non PCG graph G4 is 2-interval-PCG.
We conclude this section observing that the two theorems proved above could be of help even for graphs with a bigger number of nodes, considering large graphs that are known to be not in PCG, recognizing in them a k long sequence of either universal or almost universal nodes whose removal gives a PCG, and deducing that the original graph is at most a (k + 1)-interval-PCG.
G2, G3 and G5 are 2-interval-PCGs
In order to complete the proof that all graphs with at most 8 nodes are 2-interval-PCGs, we now generalize to 2-interval-PCGs some known results proved for PCGs in order to prove that all graphs with at most 7 nodes are PCGs [4]. More precisely, Lemma 3.1 will allow us to check the 2-interval-PCG property of a graph only on a special tree structure instead of all possible n leaf trees; Lemma 3.2 will allow us to consider only integer edge-weights and interval extremes instead of real values. The conjunction of these two simplifications makes effective the ILP model we use to solve our problem.
A full binary tree is a tree whose all internal nodes, except for its root, have a degree exactly 3.
A caterpillar is a tree for which any leaf is at a distance exactly one from a central path called spine. Caterpillars as those depicted in Figure 3 can be considered as special full binary trees (electing any internal node as root), with the exception that the root has degree 3.
In [4] it is proved that, given any n leaf tree T, there exists an edge-weighted full binary tree T* on the same leaf set with the property that, for any pair of leaves, their distance in T and in T′ is the same.
From this fact, the following result follows.
Lemma 3.1.
Let G be a 2-interval-PCG; then there exists an edge-weighted full binary tree T* and two disjoint intervals I1 and I2 such that G = 2-interval-PCG (T*, I1, I2).
The following result, deduced from [6], allows us to use only integer values both for the edge-weight function and for the extremes of the intervals.
Lemma 3.2.
Let G be a 2-interval-PCG; then there exists an edge-weighted tree T′ with integer values and two disjoint intervals I1 and I2 with integer extremes such that G = 2-interval-PCG (T′, I1, I2) and the tree structure does not change.
So, given a 2-interval-PCG, Lemma 3.1 guarantees that one of its witness trees is a full binary tree and Lemma 3.2 ensures that its edge-weight function and the two interval use integer values.
In [4] an ILP model to determine whether a given graph is a PCG with respect to a given tree structure is provided. More precisely, given a graph G and an unweighted tree T, the model determines (if they exist) an edge-weight function w for T, a bijective mapping σ between the node set V of G and the set of the leaves of T, and an interval I of the non-negative real half-line, such that G = PCG(T′, I) where T′ is the edge-weighted tree obtained from T introducing weight w and mapping σ. After this result, in other papers [2, 3], the ILP model has been made more efficient in order to work on larger graphs. Since we handle few small graphs, here we adopt the first ILP model and opportunely modify it in order to let it work for recognizing whether a graph belongs to the wider class of 2-interval-PCGs. We do not describe here our ILP model because the only change we made to the original one consisted of adapting the constraints to add the second interval. Nevertheless, for the sake of completeness, we list in the Appendix the constraints we exploited. It is worth mentioning that the same model could be further extended to a larger number of integers k and check whether a graph belongs to k-interval-PCGs, although the number of variables and constraints grows.
Finally, note that we are able to exploit such an ILP model because the 2-interval-PCG property of a graph can be checked only on full binary trees instead of all possible n leaf trees and only for integer edge-weights and intervals with integer extremes.
We apply this ILP model to G2, G3, and G5 and get the following result.
Corollary 3.3.
Non PCG graphs G2, G3 and G5 are 2-interval-PCGs.
Since the solution of the ILP model produces an edge-weighted tree and two intervals witnessing that the input graph is 2-interval-PCG, we apply it to all 7 graphs of Figure 1 with two special tree structures: complete binary trees and caterpillars. In both cases, we obtain the witness edge-weighted trees and the pairs of intervals for all the graphs: they are depicted in Figures 2 and 3. This was not obvious, indeed in [5] the authors found that all 7 node graphs are PCGs, all of them except one (the wheel) having as witness tree a caterpillar.
Conclusions
It is known that all graphs with at most 7 nodes are PCGs and hence also 2-interval-PCGs. In this note, we proved that all 8-node graphs are 2-interval-PCGs.
We conclude by observing that 9-node graphs that are not PCGs are much more than seven. In fact, in [3] only minimal PCGs (i.e., each of their induced subgraphs is a PCG) with 9 nodes are enumerated, and they are 1494. So, in order to prove (or disprove) that all 9-node graphs are 2-interval-PCGs, it does not seem possible to apply our approach, even resorting to a most efficient ILP model, as the ones described in [2, 3]. Instead, it would be interesting to check whether the ILP model extended to larger values of k > 2 could be useful to check which graphs are in k-interval-PCG. Nevertheless, before doing it, we should be able to detect small graphs that are not 2-interval-PCG, and this is currently one of the main open problems on this topic.