Some classes of graphs that are not Pairwise Compatibility Graphs (Communication) Pierluigi Baiocchi, Tiziana Calamoneri, Angelo Monti, and Rossella Petreschi Sapienza University of Rome via Salaria 113, 00198 Roma, Italy. pierluigi.baiocchi@gmail.com,{ calamo,monti,petreschi }@di.uniroma1.it 1 Introduction Graphs we deal with in this paper are motivated by a fundamental problem in computational biology, that is the reconstruction of phy- logenetic trees, i.e. trees where leaves represent known taxa while internal nodes possible ancestors that might have led through evolu- tion to this set of taxa [8]. The tree reconstruction problem is proved to be NP-hard under many criteria of optimality, moreover real phy- logenetic trees are usually huge, so testing possible heuristics on real data is in general very difficult. This is the reason why it is common to exploit sample techniques, extracting relatively small subsets of taxa from large phylogenetic trees according to some biologically- motivated constraints, and to test the reconstruction algorithms only on the smaller subtrees induced by the sample. Using in the sample very close or very distant taxa can create problems for phylogeny re- construction algorithms [5] so, in selecting a sample from the leaves of the tree, the constraint of keeping the pairwise distance between any two leaves in the sample between two given positive integers dmin and dmax is used. This motivates the introduction of pairwise compatibility graphs (PCGs). 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 . 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 ) [3, 6]. b u u 2 u u u a c 2 1 1 2 u u u u u d a d b c a. b. Fig. 1. a. A graph G. b. An edge-weighted caterpillar T such that G = P CG(T, 4, 5). 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 find a caterpillar as witness tree [2]. Due to the flexibility afforded 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 [6]. This conjecture has been confuted by proving the existence of some graphs not belonging to PCG. Namely, Yanhaona et al. [9] show a not PCG bipartite graph with 15 nodes (Figure 2.a). More recently, Durochet et al. [4] prove that there exists a not bipartite graph with 8 nodes that is not PCG (Figure 2.b); this is the smallest graph that is not PCG, since all graphs with at most 7 nodes are PCGs [2]. Subsequently, Mehnaz and Rahman [7] generalize the technique in [9] to provide a class of bipartite graphs that are not PCGs. The authors of [4] provide also an example of a planar graph with 20 nodes that is not a PCG (Figure 2.c). 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 u u u u u u u u u u u u u u u u u u u u u u u a. b. c. Fig. 2. a. The first graph proven not to be a PCG. b. The graph of smallest size proven not to be a PCG. c. A planar graph that is not PCG. Namely, we consider three classes of n-node graphs, n ≥ 8, that are all modifications 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 first 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 [10]. Finally, we deep inside the wheels as they have already been studied from the pairwise compatibility point of view. Indeed, wheel W7 is PCG and it is the only graph with 7 nodes whose witness tree is not a caterpillar [2] (see Figure 3.a). Moreover, it has been proven in [1] that also the larger wheels up to W11 do not have a caterpillar as a witness tree but, up to now, no other witness trees are known for these graphs and, in general, it has been left open to understand whether wheels with at least 8 nodes are PCGs or not. In the following section we communicate all our results concern- ing these three classes in relation to the pairwise compatibility prop- erty. All the proofs are detailed in the extended version of this paper. 2 Results Given two graphs G and H, their strong product GH 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 , v 0 ) if and v7 v6 v2 u 3 u u v4 u uv3 u uc 1 5 1 5 v5 u 1 u2 u2 u 1 3 u v2 u 3 3 3 uv1 v6 u 3 1 1 3 uv4 u u u 3 6 v3 u 1 1 uv1 u u c v5 a. b. Fig. 3. a. Tree T such that W7 = P CG(T, 5, 7); b. Tree T such that W8 = P CG(T, 9, 13). only if either u = u0 and (v, v 0 ) is an edge of H or v = v 0 and (u, u0 ) is an edge of G or both (u, u0 ) and (v, v 0 ) are edges in G and H respectively. Theorem 1. Let k ≥ 4. The graph Ck K2 is not PCG. 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. Theorem 2. Let n ≥ 8. The square of cycle Cn is not PCG. 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: Theorem 3. Wheel W8 is PCG. On the contrary, when n ≥ 8, we prove that wheels are not PCGs: Theorem 4. Let n ≥ 9. The graph Wn is not PCG. Our last results concern minimality of the previously defined classes of graphs, where a not PCG is minimal if, by deleting any node from it, we get a PCG. Theorem 5. Let k ≥ 4. The graph obtained by removing any node from Ck K2 is PCG. In other words, Ck K2 is a minimal not PCG. Theorem 6. Let k ≥ 4. The graph obtained by removing any node from C 2 is PCG. In other words, C 2 is a minimal not PCG. Theorem 7. Let n ≥ 9. The graph obtained by removing any node from Wn is PCG. In other words, Wn is a minimal not PCG. Acknowledgments This work has been partially supported by Sapienza University of Rome projects “Graph Algorithms for Phylogeny: a promising ap- proach” and “Combinatorial structures and algorithms for problems in co-phylogeny”. References 1. T. Calamoneri, A. Frangioni, B. Sinaimeri. Pairwise Compatibility Graphs of Caterpillars. The Computer Journal 57(11) 1616–1623, 2014. 2. T. Calamoneri, D. Frascaria, B. Sinaimeri. All graphs with at most seven vertices are Pairwise Compatibility Graphs. The Computer Journal 56(7) 882-886, 2013. 3. T. Calamoneri, B. Sinaimeri. On Pairwise Compatibility Graphs: a Survey. SIAM Review 58(3) 445-460, 2016. 4. S. Durocher, D. Mondal, Md. S. Ramhan. On graphs that are not PCGs. Theoret- ical Computer Science 571 78–87, 2015. 5. J. Felsenstein. Cases in which parsimony or compatibility methods will be posi- tively misleading. Systematic Zoology, 27, 401–410, 1978. 6. P.E. Kearney, J. I. Munro, D. Phillips. Efficient generation of uniform samples from phylogenetic trees. Proc. Algorithms in Bioinformatics, Lecture Notes in Computer Science 2812, 177–189, 2003. 7. S. Mehnaz and M.S. Rahman. Pairwise compatibility graphs revisited. Proc. In- ternational Conference on Informatics, Electronics Vision (ICIEV), 2013. 8. K.E. Omland. The Assumptions and Challenges of Ancestral State Reconstruc- tions. Systematic Biology, 48 (3), 604–611, 1999. 9. M.N. Yanhaona, Md.S. Bayzid, Md. S. Rahman. Discovering Pairwise Compati- bility Graphs. Discrete Mathematics, Algorithms and Applications, 2(4), 607–623, 2010. 10. M.N. Yanhaona, K.S.M. Tozammel Hossain, Md. S. Rahman. Pairwise Compati- bility Graphs. Journal of Applied Mathematics and Computing, 30, 479–503, 2009.