On star-multi-interval pairwise compatibility graphs
share
A graph G is a star-k-PCG if there exists a non-negative edge weighted star tree S and k mutually exclusive intervals I_1, I_2, … , I_k of non-negative reals such that each vertex of G corresponds to a leaf of S and there is an edge between two vertices in G if the distance between their corresponding leaves in S lies in I_1∪ I_2∪…∪ I_k. These graphs are related to different well-studied classes of graphs such as PCGs and multithreshold graphs. It is well known that for any graph G there exists a k such that G is a star-k-PCG. Thus, for a given graph G it is interesting to know which is the minimum k such that G is a star-k-PCG. In this paper we focus on classes of graphs where k is constant and prove that circular graphs and two dimensional grid graphs are both star-2-PCGs and that they are not star-1-PCGs. Moreover we show that 4-dimensional grids are at least star-3-PCGs.
READ FULL TEXT