Decomposition of complete graphs into factors of diameter two and three
Damir Vukicević
Discussiones Mathematicae Graph Theory, Tome 23 (2003), p. 37-54 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2003-01-01
EUDML-ID : urn:eudml:doc:270782 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1184,
     author = {Damir Vukicevi\'c},
     title = {Decomposition of complete graphs into factors of diameter two and three},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {23},
     year = {2003},
     pages = {37-54},
     zbl = {1035.05071},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1184}
}

Damir Vukicević. Decomposition of complete graphs into factors of diameter two and three. Discussiones Mathematicae Graph Theory, Tome 23 (2003) pp. 37-54. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1184/

[000] [1] B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).

[001] [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. | Zbl 0256.05117

[002] [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. | Zbl 0159.54203

[003] [4] D. Palumbíny, On decompositions of complete graphs into factors with equal diameters, Bollettino U.M.I. (4) 7 (1973) 420-428. | Zbl 0264.05124

[004] [5] P. Hrnciar, On decomposition of complete graphs into three factors with given diameters, Czechoslovak Math. J. 40 (115) (1990) 388-396. | Zbl 0748.05075

[005] [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. | Zbl 0213.51004

[006] [7] S. Znám, Decomposition of complete graphs into factors of diameter two, Math. Slovaca 30 (1980) 373-378. | Zbl 0462.05052

[007] [8] S. Znám, On a conjecture of Bollobás and Bosák, J. Graph Theory 6 (1982) 139-146. | Zbl 0497.05049