Pairwise compatibility graphs revisited

Shagufta Mehnaz, Md Sohel Rahman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

A graph G = (V, E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u V and there is an edge (u, v) E if and only if dmin ≤ dT(lu, lv) ≤ dmax where d T(lu, lv) is the sum of weights of the edges on the unique path from lu to lv in T. In this note, firstly, we show a class of bipartite graphs not to be PCG, that is, it is not possible to draw a pairwise compatibility tree for these graphs. Further we construct a class of more general non-PCGs each member of which contains a bipartite graph belonging to the class of graphs mentioned above as a subgraph. Secondly, we show by computational means that all the bipartite graphs with at most eight vertices are PCGs. In particular all these graphs are PCGs of a particular structure of tree called centipede.

Original languageEnglish (US)
Title of host publication2013 International Conference on Informatics, Electronics and Vision, ICIEV 2013
DOIs
StatePublished - 2013
Event2013 2nd International Conference on Informatics, Electronics and Vision, ICIEV 2013 - Dhaka, Bangladesh
Duration: May 17 2013May 18 2013

Publication series

Name2013 International Conference on Informatics, Electronics and Vision, ICIEV 2013

Conference

Conference2013 2nd International Conference on Informatics, Electronics and Vision, ICIEV 2013
Country/TerritoryBangladesh
CityDhaka
Period5/17/135/18/13

All Science Journal Classification (ASJC) codes

  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering

Cite this