|
|||||
 |
|
|
|
|
|
|
|
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 is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree with positive weights and nonnegative numbers and such that the leaves of are exactly the vertices of , and is an edge in if and only if the sum of weights of edges on the unique path between and in is at least and at most . We show that a wheel on vertices is a PCG if and only if , 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
Received: 27 September 2018
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 |
|
