Path factorizations of complete multipartite graphs

DOI10.1016/S0012-365X(98)00176-9MaRDI QIDQ1296982zbMATH OpenWikidataFDO

Authors P. Paulraja, A. Muthusamy

Publication date 9 February 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(98)00176-9

zbMATH Keywords

complete graphfactorizationpath

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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\).

Recommendations

• On path factorizations of complete multipartite graphs
• scientific article; zbMATH DE number 5823698
• Publication:4733888
• P\({}_ 3\)-factorization of complete multipartite graphs

Cites work

• \(G\)-designs and related designs
• \(P_{2p}\)-factorization of a complete bipartite graph
• Existence of resolvable path designs
• Graph theory
• scientific article; zbMATH DE number 4173021 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 3592042 (Why is no real title available?)
• On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
• On path factorizations of complete multipartite graphs
• P\({}_ 3\)-factorization of complete multipartite graphs
• Resolvable path designs

Cited in

(11)

• On path factorizations of complete multipartite graphs
• The spectrum of path factorization of bipartite multigraphs
• \(\tilde{S}_k\)-factorization of the symmetric digraph of wreath product of graphs
• scientific article; zbMATH DE number 5823698 (Why is no real title available?)
• Remarks on path factors in graphs
• scientific article; zbMATH DE number 4150220 (Why is no real title available?)
• Path-factors involving paths of order seven and nine
• P₃-factorization of triangulated Cartesian product of complete graphs
• scientific article; zbMATH DE number 5237268 (Why is no real title available?)
• Linear arboricity of the tensor products of complete multipartite graphs
• The proof of Ushio's conjecture concerning path factorization of complete bipartite graphs

This page was built for publication: Path factorizations of complete multipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1296982)