Pairwise compatibility graphs: complete characterization for wheels

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

doi:10.2140/involve.2019.12.871

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

This article is available for purchase or by subscription. See below.

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

DOI: 10.2140/involve.2019.12.871

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 $u v$ 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 \leq 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.)

PDF Access Denied

We have not been able to recognize your IP address 35.173.48.18 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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

Vol. 12, No. 5, 2019