×

On partition graphs. (English) Zbl 0545.05056

The vertex set of a partition graph \(G^ n_ 1=\Pi^ n,E_ 1)\) is formed by all partitions of an n-element set A in nonvoid subsets except the trivial partition formed by A itself. Two vertices of \(G^ n_ 1\) are joined by an edge iff the corresponding partitions have at least one common class. The author proves that for each n the partition graph \(G^ n_ 1\) is connected and for \(n>3\) its diameter is equal 3. Density of partition graphs is also studied.
Reviewer: H.Kramer

MSC:

05C99 Graph theory
05C40 Connectivity
PDFBibTeX XMLCite