Pairwise compatibility graphs: complete characterization for wheels
Matthew T Beaudouin-Lafon, Serena Chen, Nathaniel J. Karst, Denise Sakai Troxell, Xudong Zheng · Involve a Journal of Mathematics · 2019
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.)