Discovering Pairwise Compatibility Graphs
Discovering Pairwise Compatibility Graphs
复制标题
发现成对兼容性图
DOI：
10.1142/s1793830910000917
复制
发表时间：
2010
影响因子：
1
通讯作者：
M. S. Rahman
中科院分区：
文献类型：
--
作者：
Muhammad N. Yanhaona;Md. Shamsuzzoha Bayzid;M. S. Rahman
设T为边加权树，dT （u, v）为T中从u到v路径上的边的权值之和，设dmin和dmax为两个非负实数，使得dmin≤dmax。则T对于dmin和dmax的配对相容图是一个图G = (V，E)，其中每个顶点u′∈V对应于T的叶子u，且当且仅当dmin≤dT (u， V) = dmax存在一条边（u′，V′）∈E。如果存在边加权树T和两个非负实数dmin和dmax，且G是T对于dmin和dmax的成对相容图，则图G称为成对相容图（PCG）。Kearney等人推测每个图都是一个PCG bb0。在本文中，我们通过证明并非所有的图都是PCGs来反驳这个猜想。我们还证明了众所周知的树功率图和它们的一些扩展是pcg。
Let T be an edge weighted tree, let dT (u, v) be the sum of the weights of the edges on the path from u to v in T, and let dmin and dmax be two nonnegative real numbers such that dmin ≤ dmax. Then a pairwise compatibility graph of T for dmin and dmax is a graph G = (V,E), where each vertex u′ ∈ V corresponds to a leaf u of T and there is an edge (u′, v′) ∈ E if and only if dmin ≤ dT (u, v) = dmax. A graph G 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 G is a pairwise compatibility graph of T for dmin and dmax. Kearney et al. conjectured that every graph is a PCG [3]. In this paper, we refute the conjecture by showing that not all graphs are PCGs. We also show that the well known tree power graphs and some of their extensions are PCGs.