论文标题
精确 - $ 2 $ - 汇总图
Exact-$2$-Relation Graphs
论文作者
论文摘要
最近已使用具有非负整数边缘权重的成对兼容图（PCG）来描述具有水平基因转移的罕见进化事件和场景。在这里，我们考虑以下情况：顶点完全由两个离散事件隔开：给定一个带叶子的树$ t $ set $ l $和edge-weights $λ：e（t）\ to \ mathbb {n} _0 $，非阴性integer integer integer integer compatibility compatibility pairwise pairwise papatibility pairwise graph $每当沿着$ x $到$ t $ in $ t $的唯一路径的非阴性整数权重的总和等于$ 2 $。图$ g $的表示为$ \ textrm {nnipcg}（t，λ，2,2）$，并且仅当其点取决于点的商$ g/\！\ rthin $是一个块图形，其中有两个顶点在$ g $中具有相同的社区，则有两个顶点$ \ rthin $。如果$ g $是这种类型的，则可以有效地构建标有树$（t，λ）$。此外，我们考虑了此类图的面向版本。
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 $λ: E(T)\to\mathbb{N}_0$, the non-negative integer pairwise compatibility graph $\textrm{nniPCG}(T,λ,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 $\textrm{nniPCG}(T,λ,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,λ)$ explaining $G$ can be constructed efficiently. In addition, we consider an oriented version of this class of graphs.
