Pairwise compatibility graphs: complete characterization for wheels

A simple graph G is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T with positive weights and nonnegative numbers d_min and d_max such that the leaves of T are exactly the vertices of G, and uv is an edge in G if and only if the sum of weights of edges on the unique path between u and v in T is at least d_min and at most d_max. We show that a wheel on n vertices is a PCG if and only if n ≤ 8, settling an open problem proposed by Calamoneri and Sinaimeri (SIAM Review 58:3 (2016), 445–460). Our approach is based on unavoidable binary classifications of the edges in the complement of wheels that are PCGs. (Note: during the review process of our work, we learned that the same result has been obtained independently with an alternative proof.).