Conference
Version
T. Calamoneri, R. Petreschi
A graph $G=(V,E)$ is called a {\em 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} \leq d_{max}$, such that $V$ coincides with the set of leaves of $T$, and there is an edge $(u,v) \in E$ if and only if $d_{min} \leq d_{T,w} (u, v) \leq 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. It is known that $LPG \cap mLPG$ is not empty and that threshold graphs are one of the classes contained in it. It is also known that threshold graphs are all the graphs with Dilworth number one, where the {\em Dilworth number} of a graph is the size of the largest subset of its vertices in which the close neighborhood of no vertex contains the neighborhood of another. In this paper we do one step ahead toward the comprehension of the structure of the set $LPG \cap mLPG$, proving that graphs with Dilworth number two belong to this intersection.
PDF Files