CHARACTERIZATIONANDALGORITHMDESIGN FORSOMESUBCLASSESANDSUPERCLASSESOF PAIRWISECOMPATIBILITYGRAPHS

Abstract

A graph G = (V,E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf u of T corresponds to a vertex u ∈ V 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 from u to v in T. The tree T is called the pairwise compatibility tree (PCT) of G. The pairwise compatibility graph recognition problem refers to the problem where we need to prove whether a graph is a pairwise compatibility graph or not. There are some relaxed versions of the problem which lead to some superclasses and some constrained versions of the problem which lead to some subclasses of pairwise compatibility graphs. Also there is a necessary condition and a sufficient condition for a graph being a PCG and there are four classes of graphs intermediate to the necessary condition and the sufficient condition. The applications of PCGs have been well known in the field of Bioinformatics and Computational Biology where we can use this concept for phylogenetic tree reconstruction and explaining rare evolutionary events among the species. A recent research work also showed that the concept of PCGs can be applied to unmanned aerial vehicles (UAV) based automated traffic management scheme based on blockchain assisted by multi-access edge computing (MEC). In this research work, we focus on finding the pairwise compatibility properties of grid graphs, a superclass of grid graphs and two of the four graph classes intermediate to the necessary condition and the sufficient condition. We prove that grid graphs are PCGs, a superclass of grid graph is a 2-interval PCG, the two of the four graph classes intermediate to the necessary condition and the sufficient condition are not PCGs. We also find a new subclass, simgular pairwise compatibility graph (SPCG), by applying a constraint on PCGs, where in the interval [dmin,dmax], dmin = dmax. We give a complete characterization of star SPCG and find some graphs that belong to caterpillar SPCG. Furthermore, we propose an application of the concept of PCG in vehicular ad-hoc networks (VANET).