Pairwise Compatibility Graphs of Caterpillars
Pairwise Compatibility Graphs of Caterpillars
复制标题
毛毛虫的成对兼容性图
DOI：
10.1093/comjnl/bxt068
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
B. Sinaimeri
中科院分区：
文献类型：
--
作者：
T. Calamoneri;A. Frangioni;B. Sinaimeri
一个图G =（V，E）称为成对相容图（PCG），如果存在一个边权树T和两个非负的真实的实数dmin和dmax，使得T的每一个叶lu对应于V的一个顶点u，并且在E中存在一条边（u，v）当且仅当dmin <= dT，w（lu，lv）<= dmax，其中dT，w（lu，lv），lv）是T中从lu到lv的唯一路径上的边的权重之和。在本文中，我们把注意力集中在PCG的见证树是一个毛毛虫。我们首先给出了一些性质的图，是一个毛毛虫的PCG。我们制定这个问题作为一个整数线性规划问题，我们利用这一提法表明，车轮上的n个顶点Wn，n = 7，.，11，见证树不可能是毛毛虫。与此相关的结果，我们推测，没有车轮是一个毛毛虫的PCG。最后，我们陈述了一个更一般的结果，证明了任何两两相容图都允许一个满二叉树作为证明树T。
A graph G = (V, E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u of V and there is an edge (u, v) in E if and only if dmin <= dT,w(lu, lv) <= dmax where dT,w(lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices Wn, n = 7, ... , 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any pairwise compatibility graph admits a full binary tree as witness tree T.