DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 18(2) (1998) 233-242
DOI: 10.7151/dmgt.1079

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.

Received 9 March 1998
Revised 3 August 1998