Journal
Version
T. Calamoneri, A. Frangioni, B. Sinaimeri
A graph $G$ 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 \in V$ and there is an edge $(u,v) \in E$ if and only if $d_{min} \leq d_{T,w} (l_u, l_v) \leq 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 concentrate on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. Then, we reformulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheel on $7$ vertices $W_7$, its witness tree cannot be a caterpillar. Finally, we turn our attention to PCGs of a general tree and prove that all of them admit as witness tree $T$ a full binary tree (i.e. a tree in which every vertex other than the leaves has two children), whose root and its two incident edges have been merged in a unique edge.
PDF Files