Exact-$2$-Relation Graphs

Abstract

Pairwise compatibility graphs (PCGs) with non-negative integer edge weights recently have been used to describe rare evolutionary events and scenarios with horizontal gene transfer. Here we consider the case that vertices are separated by exactly two discrete events: Given a tree $T$ with leaf set $L$ and edge-weights $\lambda :E(T)\to {\mathbb{N}}_0$, the non-negative integer pairwise compatibility graph $\text{nniPCG}(T,\lambda ,2,2)$ has vertex set $L$ and $xy$ is an edge whenever the sum of the non-negative integer weights along the unique path from $x$ to $y$ in $T$ equals $2$. A graph $G$ has a representation as $\text{nniPCG}(T,\lambda ,2,2)$ if and only if its point-determining quotient $G/\!\rthin$ is a block graph, where two vertices are in relation $\rthin$ if they have the same neighborhood in $G$. If $G$ is of this type, a labeled tree $(T,\lambda )$ explaining $G$ can be constructed efficiently. In addition, we consider an oriented version of this class of graphs.