All graphs with at most seven vertices are Pairwise Compatibility Graphs

T. Calamoneri, D. Frascaria, 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 dmin and dmax such that each leaf l_u of T corresponds to a vertex u of V and there is an edge (u, v) of E if and only if dmin ² dT,w(l_u, l_v) ² dmax where dT,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 are PCGs of a particular structure of a tree: a centipede.

PDF File and Results

Journal Version

link to all the results