# 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*of

_{u}*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*) is the sum of the weights of the edges on the unique path from

_{v}*l*to

_{u}*l*in

_{v}*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*.