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 u of V and there is an edge (u, v) in E if and only if d_min <= d_T,w(l_u, l_v) <= 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, ... , 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 pairwise compatibility graph admits a full binary tree as witness tree T.