ArticleOriginal scientific text

Title

Decomposition of complete graphs into factors of diameter two and three

Authors 1

Affiliations

  1. Department of Mathematics, University of Split, Teslina 12, 21000 Split, Croatia

Abstract

We analyze a 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. We find exact values for k ≤ 4 and the asymptotic value of the ratio of this number and k when k tends to infinity. We also find the asymptotic value of the ratio of 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 and number k when p is fixed.

Keywords

decomposition, graph

Bibliography

  1. B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).
  2. J. Bosák, Disjoint factors of diameter two in complete graphs, J. Combin. Theory (B) 16 (1974) 57-63, doi: 10.1016/0095-8956(74)90095-1.
  3. J. Bosák, A. Rosa and S. Znám, On decompositions of complete graphs into factors with given diameters, in: Proc. Colloq. Tihany (Hung), (1968) 37-56.
  4. D. Palumbíny, On decompositions of complete graphs into factors with equal diameters, Bollettino U.M.I. (4) 7 (1973) 420-428.
  5. P. Hrnciar, On decomposition of complete graphs into three factors with given diameters, Czechoslovak Math. J. 40 (115) (1990) 388-396.
  6. N. Sauer, On factorization of complete graphs into factors of diameter two, J. Combin. Theory 9 (1970) 423-426, doi: 10.1016/S0021-9800(70)80096-5.
  7. S. Znám, Decomposition of complete graphs into factors of diameter two, Math. Slovaca 30 (1980) 373-378.
  8. S. Znám, On a conjecture of Bollobás and Bosák, J. Graph Theory 6 (1982) 139-146.
Pages:
37-54
Main language of publication
English
Received
2001-05-25
Accepted
2002-09-05
Published
2003
Exact and natural sciences