Halving complete 4-partite graphs. (English) Zbl 0994.05117

Fronček, Dalibor; Širáň, Jozef

Ars Comb. 55, 44-63 (2000).

Factor of a graph \(G\) is a subgraph of \(G\) containing each vertex of \(G\). Factors of \(G\) are said to form a decomposition of \(G\) if their edge sets partition the edge set of \(G\).
The authors completely determine the spectrum (i.e. set of orders) of complete 4-partite graphs with at most one odd part which are decomposable into two isomorphic factors with a finite diameter. For complete 4-partite graphs with all parts odd the authors solve the spectrum problem completely for factors with diameter 5 and partially for the remaining possible finite diameters (2, 3, and 4).
This problem was solved earlier by P. Híc and D. Palumbíny for complete graphs [Math. Slovaca 37, 247-254 (1987; Zbl 0675.05051)], and by D. Fronček for complete bipartite and tripartite graphs [Graphs Comb. 12, 305-320 (1996; Zbl 0866.05050)].

Reviewer: Robert Babilon (Praha)

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

factorization; factor; halving; complete graph; multipartite graph; complete multipartite graph

Citations:

Zbl 0675.05051; Zbl 0866.05050