A complete tripartite graph without one edge, K̃m1, m2, m3 is called almost complete tripartite graph. A graph K̃m1, m2, m3 that can be decomposed into two isomorphic factors with a given diameter d is called d-halvable. We prove that K̃m1, m2, m3 is d-halvable for a finite d only if d ≤ 5 and completely determine all triples 2m′1 + 1, 2m′2 + 1, 2m′3 for which there exist d-halvable almost complete tripartite graphs for diameters 3,4 and 5, respectively.
Bibliographical noteFunding Information:
E-mail addresses: firstname.lastname@example.org, email@example.com (D. Fronc$ek). 1Current address: Department of Mathematics and Statistics, University of Vermont, 16 Colchester Avenue, Burlington, VT 05401, USA. 2This work was in part supported by CACR$ Grant No. 201/98/1451.
- Graph decompositions
- Isomorphic factors
- Self-complementary graphs