Conference
Version
T. Calamoneri, R. Petreschi
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 one. In this paper we give a new characterization of Dilworth k graphs, for each value of k, exactly defining their structure. Moreover, we put these graphs in relation with {\em pairwise compatibility graphs (PCGs)}, i.e. graphs on $n$ nodes that can be generated from an edge-weighted tree T that has n leaves, each representing a different node of the graph; two nodes are adjacent in the graph if and only if the weighted distance in the corresponding T is between two given non-negative real numbers, m and M. When either m or M are not used to eliminate edges from $G$, the two subclasses {\em leaf power} and {\em minimum leaf power graphs} (LPGs and mLPGs, respectively) are defined. Here we prove that graphs that are either LPGs or mLPGs of trees obtained connecting the centers of k stars with a path are Dilworth k graphs. We show that the opposite is true when k=1,2, but not when k \geq 3. Finally, we show that the relations we proved between Dilworth k graphs and chains of k stars hold only for LPGs and mLPGs, but not for PCGs.
PDF Files