Pairwise compatibility graph

In graph theory, a graph ${\displaystyle G}$ is a pairwise compatibility graph (PCG) if there exists a tree ${\displaystyle T}$ and two non-negative real numbers ${\displaystyle d_{min}<d_{max}}$ such that each node ${\displaystyle u'}$ of ${\displaystyle G}$ has a one-to-one mapping with a leaf node ${\displaystyle u}$ of ${\displaystyle T}$ such that two nodes ${\displaystyle u'}$ and ${\displaystyle v'}$ are adjacent in ${\displaystyle G}$ if and only if the distance between ${\displaystyle u}$ and ${\displaystyle v}$ are in the interval ${\displaystyle [d_{min},d_{max}]}$.^[1]

Graph (b) that is pairwise compatibility graphs of the trees (a) and (c)

Graphs that are not pairwise compatibility graphs

The subclasses of PCG include graphs of at most seven vertices, cycles, forests, complete graphs, interval graphs and ladder graphs.^[1] However, there is a graph with eight vertices that is known not to be a PCG.^[2]