Exploring pairwise compatibility graphs
Exploring pairwise compatibility graphs
复制标题
探索成对兼容性图
DOI：
10.1016/j.tcs.2012.11.015
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
B. Sinaimeri
中科院分区：
文献类型：
--
作者：
T. Calamoneri;Eugenio Montefusco;R. Petreschi;B. Sinaimeri
图G=(V，E)称为成对相容图(PCG)，如果存在树T、T上的正边权函数w和两个非负实数dmin≤dmax，使得每个叶子luof T对应于顶点u∈V并且存在边(u，v)∈E当且仅当dmin≤dT，w(lu，lv)≤dmax其中dt，w(lu，Lv)是从luto lvin T唯一路径上的边的权重之和。本文分析了两个特殊子类之间的PCG类，这两个子类是由叶对之间的距离约束仅与dmax(Lpg)或dmin(Mlpg)有关的情况而产生的。特别地，我们证明了LPG和mLPG类的并不与整个PCG类重合，它们的交不是空的，并且LPG和mLPG类都不包含在另一个类中。最后，我们研究了PCG、mLPG和LPG类在几种常见的图运算下的闭包性质。特别地，我们考虑了如下操作：添加孤立或全能顶点，添加悬挂顶点，添加假孪生或真孪生，取图的补和两图的不相交并。
A graph G=(V,E) is called a pairwise compatibility graph (PCG) if there exists a tree T, a positive edge weight function w on T, and two non-negative real numbers dmin≤dmax, such that each leaf luof T corresponds to a vertex u∈V and there is an edge (u,v)∈E if and only if dmin≤dT,w(lu,lv)≤dmaxwhere dT,w(lu,lv) is the sum of the weights of the edges on the unique path from luto lvin T. In this paper we analyze the class of PCGs in relation to two particular subclasses resulting from the cases where the constraints on the distance between the pairs of leaves concern only dmax(LPG) or only dmin(mLPG). In particular, we show that the union of LPG and mLPG classes does not coincide with the whole class of PCGs, their intersection is not empty, and that neither of the classes LPG and mLPG is contained in the other. Finally, we study the closure properties of the classes PCG, mLPG and LPG, under some common graph operations. In particular, we consider the following operations: adding an isolated or universal vertex, adding a pendant vertex, adding a false or a true twin, taking the complement of a graph and taking the disjoint union of two graphs.