Geodesic
2-halvable complete 4-partite graphs
Discussiones Mathematicae. Graph Theory, Tome 18 (1998) no. 2, pp. 233-242.

Voir la notice de l'article provenant de la source Library of Science

A complete 4-partite graph K_m₁,m₂,m₃,m₄ is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs K_m₁,m₂,m₃,m₄ with at most one odd part all d-halvable graphs are known. In the class of biregular graphs K_m₁,m₂,m₃,m₄ with four odd parts (i.e., the graphs K_m,m,m,n and K_m,m,n,n) all d-halvable graphs are known as well, except for the graphs K_m,m,n,n when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs K_m₁,m₂,m₃,m₄ with three or four different odd parts.
Keywords: Graph decompositions, isomorphic factors, selfcomplementary graphs 
@article{DMGT_1998_18_2_a9,
     author = {Fron\v{c}ek, Dalibor},
     title = {2-halvable complete 4-partite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {233--242},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {1998},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a9/}
}
TY  - JOUR
AU  - Fronček, Dalibor
TI  - 2-halvable complete 4-partite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1998
SP  - 233
EP  - 242
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a9/
LA  - en
ID  - DMGT_1998_18_2_a9
ER  - 
%0 Journal Article
%A Fronček, Dalibor
%T 2-halvable complete 4-partite graphs
%J Discussiones Mathematicae. Graph Theory
%D 1998
%P 233-242
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a9/
%G en
%F DMGT_1998_18_2_a9
Fronček, Dalibor. 2-halvable complete 4-partite graphs. Discussiones Mathematicae. Graph Theory, Tome 18 (1998) no. 2, pp. 233-242. http://geodesic.mathdoc.fr/item/DMGT_1998_18_2_a9/

[1] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber Schmidt, Boston, 1979).

[2] J. Bosák, A. Rosa and Š. Znám, On decompositions of complete graphs into factors with given diameters, in: Theory of Graphs, Proc. Coll. Tihany 1966 (Akadémiai Kiadó, Budapest, 1968) 37-56.

[3] D. Fronček, Decompositions of complete bipartite and tripartite graphs into selfcomplementary factors with finite diameters, Graphs. Combin. 12 (1996) 305-320, doi: 10.1007/BF01858463.

[4] D. Fronček, Decompositions of complete multipartite graphs into selfcomplementary factors with finite diameters, Australas. J. Combin. 13 (1996) 61-74.

[5] D. Fronček, Decompositions of complete multipartite graphs into disconnected selfcomplementary factors, Utilitas Mathematica 53 (1998) 201-216.

[6] D. Fronček and J. Širáň, Halving complete 4-partite graphs, Ars Combinatoria (to appear).

[7] T. Gangopadhyay, Range of diameters in a graph and its r-partite complement, Ars Combinatoria 18 (1983) 61-80.

[8] P. Híc and D. Palumbíny, Isomorphic factorizations of complete graphs into factors with a given diameter, Math. Slovaca 37 (1987) 247-254.

[9] A. Kotzig and A. Rosa, Decomposition of complete graphs into isomorphic factors with a given diameter, Bull. London Math. Soc. 7 (1975) 51-57, doi: 10.1112/blms/7.1.51.

[10] D. Palumbíny, Factorizations of complete graphs into isomorphic factors with a given diameter, Zborník Pedagogickej Fakulty v Nitre, Matematika 2 (1982) 21-32.

[11] P. Tomasta, Decompositions of graphs and hypergraphs into isomorphic factors with a given diameter, Czechoslovak Math. J. 27 (1977) 598-608.

[12] E. Tomová, Decomposition of complete bipartite graphs into factors with given diameters, Math. Slovaca 27 (1977) 113-128.