# 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

## 2-HALVABLE COMPLETE 4-PARTITE GRAPHS

Dalibor Fronček

Department of Applied Mathematics
Technical University Ostrava
17 listopadu, 708 33 Ostrava, Czech Republic

e-mail: dalibor.froncek@vsb.cz

## Abstract

A complete 4-partite graph Km1,m2,m3,m4 is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs Km1,m2,m3,m4 with at most one odd part all d-halvable graphs are known. In the class of biregular graphs Km1,m2,m3,m4 with four odd parts (i.e., the graphs Km,m,m,n and Km,m,n,n) all d-halvable graphs are known as well, except for the graphs Km,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 Km1,m2,m3,m4 with three or four different odd parts.

Keywords: Graph decompositions, isomorphic factors, selfcomplementary graphs.

1991 Mathematics Subject Classification: 05C70.

## References

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