Pairwise Compatibility Graphs of Caterpillars

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 d(min) and d(max) such that each leaf l(u) of T corresponds to a vertex uaV and there is an edge (u, v)aE if and only if d(min) a parts per thousand currency sign d(T,w) (l(u), l(v)) a parts per thousand currency sign d(max), where d(T,w) (l(u), l(v)) is the sum of the weights of the edges on the unique path from l(u) to l(v) in T. In this paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices W-n, n=7, aEuro broken vertical bar, 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any PCG admits a full binary tree as witness tree T.