×

Decomposition of complete graphs into factors of diameter two and three. (English) Zbl 1035.05071

Consider the problem of finding the minimum number of vertices of a complete graph that can be decomposed into one factor of diameter 2 and \(k\) factors of diameter at most 3. The author finds the exact values for \(k<5\) and the asymptotic value of the ratio of this number and \(k\), when \(k\) tends to infinity. Consider another problem of finding the number of vertices of the smallest complete graph that can be decomposed into \(p\) factors of diameter 2 and \(k\) factors of diameter 3, for fixed \(p\). The author finds the asymptotic value of the ratio of this number and \(k\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link