On star-multi-interval pairwise compatibility graphs

A graph G is a star-k-PCG if there exists a non-negative edge weighted star tree S and k mutually exclusive intervals I1,I2,…,Ik 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 I1∪I2∪…∪Ik . 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 not star-2-PCG.