All graphs with at most seven vertices are Pairwise Compatibility Graphs

Abstract

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}\le d_{T,w}(l_u,l_v)\le 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 note, we show that all the graphs with at most seven vertices are PCGs. In particular all these graphs except for the wheel on 7 vertices $W_7$ are PCGs of a particular structure of a tree: a centipede.

8 pages, 2 figures