×

zbMATH — the first resource for mathematics

Decompositions of complete graphs into factors with diameter two. (English) Zbl 0213.51003
Let \(f(k)\) be the smallest integer \(n\) so that the complete graph \(\langle n \rangle\) can be decomposed into \(k\) edge disjoint subgraphs of diameter \(2\). The authors prove: (1) \(f(k)<\left({49 \over 10} \right)^2k^2 \log k\). Recently N. Sauer considerably improved (1) by showing \(f(k)<7k\) [cf. the paper reviewed below, J. Comb. Theory 9, 423-426 (1970; Zbl 0213.51004)].

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
References:
[1] Bosák J., Rosa A., Znám Š.: On decompositions of complete graphs into factors with given diameters. Theory of Graphs, Proc. Colloq. Tihany 1966, Akadémiai Kiadó, Budapest 1968, 37 - 56. · Zbl 0159.54203
[2] Erdös P., Rényi A.: On the evolution of random graphs. Magyar tud. akad. Mat. kutató int. közl. 5 (1960), 17 61.
[3] Erdös P., Rényi A.: Additive properties of random sequences of positive integers. Acta Arithm. 6 (1960), 83-110. · Zbl 0091.04401
[4] Erdös P., Rényi A.: Egg gráfelméleti problémáról. Magyar tud. akad. Mat. kutató int. közl. 7 (1962), 623-641.
[5] Виноградов И. М.: Основы мєоруу чусєл. ГИТТЛ, Москва-Лєнинград 1952.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.