#### Vol. 12, No. 5, 2019

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Pairwise compatibility graphs: complete characterization for wheels

### Matthew Beaudouin-Lafon, Serena Chen, Nathaniel Karst, Denise Sakai Troxell and Xudong Zheng

Vol. 12 (2019), No. 5, 871–882
##### Abstract

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\le 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.)

##### Keywords
pairwise compatibility graph, PCG, phylogenetic tree, wheel
##### Mathematical Subject Classification 2010
Primary: 05C12, 05C78
##### Milestones
Revised: 28 January 2019
Accepted: 30 January 2019
Published: 22 May 2019

Communicated by Ann N. Trenk
##### Authors
 Matthew Beaudouin-Lafon Franklin W. Olin College of Engineering Needham, MA United States Serena Chen Franklin W. Olin College of Engineering Needham, MA United States Nathaniel Karst Mathematics and Sciences Division Babson College Babson Park, MA United States Denise Sakai Troxell Mathematics and Sciences Division Babson College Babson Park, MA United States Xudong Zheng Johns Hopkins University Baltimore, MD United States