Some Reduction Operations to Pairwise Compatibility Graphs

Abstract

A graph \(G=(V,E)\) with a vertex set \(V\) and an edge set \(E\) is called a pairwise compatibility graph (PCG, for short) if there are a tree \(T\) whose leaf set is \(V\), a non-negative edge weight \(w\) in \(T\), and two non-negative reals \(d_{\min}\leq d_{\max}\) such that \(G\) has an edge \(uv\in E\) if and only if the distance between \(u\) and \(v\) in the weighted tree \((T,w)\) is in the interval \([d_{\min}, d_{\max}]\). PCG is a new graph class motivated from bioinformatics. In this paper, we give some necessary and sufficient conditions for PCG based on cut-vertices and twins, which provide reductions among PCGs. Our results imply that complete \(k\)-partite graph, cactus, and some other graph classes are subsets of PCG.