Effects of graph operations on star pairwise compatibility graphs

A graph is defined as a star- -pairwise compatibility graph (PCG) when it is possible to assign a positive real number weight to each vertex ⁠, and define distinct intervals ⁠, in such a way that there is an edge in if and only if the sum of the weights of vertices and falls within the union of these intervals. The star- -PCG class is connected to two significant graph categories: PCGs and multithreshold graphs. The star number of a graph ⁠, is the smallest for which is a star- -PCG. In this paper, we study the effects of various graph operations, such as the addition of twins, pendant vertices, universal vertices, or isolated vertices, on the star number of the graph resulting from these operations. As significant applications of our findings, we determine the star number of lobster graphs and provide an upper bound for the star number of acyclic graphs. This is particularly interesting as determining the star number is notoriously difficult and is known only for a few classes of graphs. Indeed, for acyclic graphs, the exact value of the star number is currently known only for caterpillars [1].