All Graphs with at Most Seven Vertices are Pairwise Compatibility Graphs

作者：Calamoneri Tiziana; Frascaria Dario; Sinaimeri Blerina^*

来源：Computer Journal, 2013, 56(7): 882-886.

DOI：10.1093/comjnl/bxs087

• pairwise compatibility graphs
• caterpillar
• centipede
• wheel

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 is an element of V and there is an edge (u, v)is an element of E if and only if d(min) < d(T,w) (l(u), l(v)) < 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 seven vertices W-7 are PCGs of a particular structure of a tree: a centipede.

• 出版日期2013-7