All graphs with at most seven vertices are Pairwise compatibility graphs

A graph G is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u∈V and there is an edge (u, v)∈E if and only if dmin ≤ dT,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv 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 seven vertices W 7 are PCGs of a particular structure of a tree: a centipede. © 2012 The Author 2012. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.