On star-multi-interval pairwise compatibility graphs

Abstract

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, \ldots , 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\cup I_2\cup\ldots \cup 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.