Path factorizations of complete multipartite graphs
type: Item
instance of: scholarly article
title: Path factorizations of complete multipartite graphs
zbMATH Open document ID: 0930.05078
DOI: 10.1016/S0012-365X(98)00176-9
author: P. Paulraja
author: A. Muthusamy
published in: Discrete Mathematics
publication date: 2000-02-09T00:00:00Z
review text: A \(P_k\)-factor of a graph \(G\) is a spanning subgraph such that each component of it is a path on \(k\) vertices. A graph has a \(P_k\)-factorization if its edges can be partitioned into \(P_k\)-factors. It is shown that the necessary conditions \(mn\equiv 0\pmod k\) and \((m-1)nk\equiv 0\pmod{2(k-1)}\) for the wreath product of \(K_m\) and \(\overline K_n\) to have a \(P_k\)-factorization are sufficient when \(k= p+1\), \(p\) a prime, where \(\overline K_n\) is the complement of the complete graph \(K_n\).
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1320586
zbMATH Keywords: factorization
zbMATH Keywords: complete graph
zbMATH Keywords: path
MaRDI profile type: Publication
Wikidata QID: Q114122931
cites work: Q3197858
cites work: Q4101884
cites work: On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
cites work: Existence of resolvable path designs
cites work: Q5422499
cites work: Resolvable path designs
cites work: Q4159097
cites work: \(G\)-designs and related designs
cites work: P\({}_ 3\)-factorization of complete multipartite graphs
cites work: \(P_{2p}\)-factorization of a complete bipartite graph
cites work: On path factorizations of complete multipartite graphs
description: scientific article; zbMATH DE number 1320586