Abstract
A graph G=(V,E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers `d' and `D' such that each leaf `u' of T is a node of V and the edge `(u,v) belongs to E' iff `d <= d_T(u, v) <= D' where d_T(u, v) is the sum of weights of the edges on the unique path from `u' to `v' in T. The main issue on these graphs consists in characterizing them. In this note we prove the inclusion in the PCG class of threshold tolerance graphs and the non-inclusion of a number of intersection graphs, such as disk and grid intersection graphs, circular arc and tolerance graphs. The non-inclusion of some superclasses (trapezoid, permutation and rectangle intersection graphs) follows.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.