On pairwise compatibility graphs having Dilworth number two

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 d(min) and d(max), d(min) <= d(max), such that V coincides with the set of leaves of T, and there is an edge (u, v) is an element of E if and only if d(min) <= d(T,w)(u, v) <= d(max) where d(T,w)(u, v) is the sum of the weights of the edges on the unique path from u to v in T. When the constraints on the distance between the pairs of leaves concern only d(max) or only d(min) the two subclasses LPGs (Leaf Power Graphs) and mLPGs (minimum Leaf Power Graphs) are defined. The Dilworth number of a graph is the size of the largest subset of its nodes in which the close neighborhood of no node contains the neighborhood of another. It is known that LPG boolean AND mLPG is not empty and that threshold graphs, i.e. Dilworth one graphs, are contained in it. In this paper we prove that Dilworth two graphs belong to the set LPG boolean AND mLPG, too. Our proof is constructive since we show how to compute all the parameters T, w, d(max) and d(min) exploiting the usual representation of Dilworth two graphs in terms of node weight function and thresholds. For graphs with Dilworth number two that are also split graphs, i.e. split permutation graphs, we provide another way to compute T, w, d(min) and d(max) when these graphs are given in terms of their intersection model. (C) 2013 Elsevier B.V. All rights reserved.