DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

DECOMPOSITION OF COMPLETE GRAPHS INTO FACTORS OF DIAMETER TWO AND THREE

Damir Vukicević

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.

2000 Mathematics Subject Classification: 05C70.

References

 [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.