A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs

Authors

  • Md. Iqbal Hossain
  • Sammi Abida Salma
  • Md. Saidur Rahman
  • Debajyoti Mondal

DOI:

https://doi.org/10.7155/jgaa.00419

Keywords:

graph theory , pairwise compatibility graph , bipartite graph , phylogenetic tree , chordless cycle

Abstract

In this paper we give a necessary condition and a sufficient condition for a graph to be a pairwise compatibility graph (PCG). Let $G$ be a graph and let $G^c$ be the complement of $G$. We show that if $G^c$ has two disjoint chordless cycles then $G$ is not a PCG. On the other hand, if $G^c$ has no cycle then $G$ is a PCG. Our conditions are the first necessary condition and the first sufficient condition for pairwise compatibility graphs in general. We also show that there exist some graphs in the gap of the two conditions which are not PCGs.

Downloads

Download data is not yet available.

Downloads

Published

2017-02-01

How to Cite

Hossain, M. I., Salma, S. A., Rahman, M. S., & Mondal, D. (2017). A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs. Journal of Graph Algorithms and Applications, 21(3), 341–352. https://doi.org/10.7155/jgaa.00419