Decomposition of almost complete tripartite graphs into two isomorphic factors of fixed diameter

AbstractAn almost complete tripartite graph K˜m1,m2,m3 is obtained by removing an edge from the complete tripartite graph Km1,m2,m3. A graph that can be decomposed into two isomorphic factors of diameter d is d-halvable.Fronček classified all 4-halvable almost complete tripartite graphs of even order in which the missing edge has its endpoints in two partite sets of odd order. In this paper, we classify 4-halvable almost complete tripartite graphs of even order for which the missing edge has an endpoint in a partite set with an even number of vertices. We also classify all 4-halvable almost complete tripartite graphs of odd order. Finally, we give a partial classification of 3- and 5-halvable almost complete tripartite graphs