ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Mathematicae Graph Theory 18(2) (1998) 233-242DOI: 10.7151/dmgt.1079
Department of Applied Mathematics
Technical University Ostrava
17 listopadu, 708 33 Ostrava, Czech Republic
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.
Received 9 March 1998
Revised 3 August 1998