All graphs with at most seven vertices are Pairwise Compatibility Graphs
All graphs with at most seven vertices are Pairwise Compatibility Graphs
复制标题
所有最多具有七个顶点的图都是成对兼容性图
DOI：
10.1093/comjnl/bxs087
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
B. Sinaimeri
中科院分区：
文献类型：
--
作者：
T. Calamoneri;Dario Frascaria;B. Sinaimeri
一个图G$称为成对相容图（PCG $），如果存在一个边权树T$和两个非负的真实的实数$d_{min}$和$d_{max}$使得$T$的每个叶子$l_u$对应于V$中的一个顶点$u \，并且存在E$中的一条边$（u，v）\当且仅当$d_{min} \leq d_{T，w}（l_u，l_v）\leq d_{max}$其中$d_{T，w}（l_u，l_v）$是$T$中从$l_u$到$l_v$的唯一路径上的边的权重之和。
本文证明了顶点数不超过7的图都是PCG。特别地，除了7个顶点上的轮$W_7$之外，所有这些图都是树的特定结构的PCG：蜈蚣。
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 \in V$ and there is an edge $(u,v) \in E$ if and only if $d_{min} \leq d_{T,w} (l_u, l_v) \leq 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 7 vertices $W_7$ are PCGs of a particular structure of a tree: a centipede.