P\({}_ 3\)-factorization of complete multipartite graphs (Q920114)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | P\({}_ 3\)-factorization of complete multipartite graphs |
scientific article |
Statements
P\({}_ 3\)-factorization of complete multipartite graphs (English)
0 references
1989
0 references
Let G and H be graphs. A spanning subgraph F of G is called an H-factor if and only if each component of F is isomorphic to H. If G is expressible as an edge-disjoint sum of H-factors then this sum is called an H-factorization of G. Let \(P_ 3\) be a path of order three and let K(m,n) be a complete multipartite graph with m partite set of n vertices each (m\(\geq 2,n\geq 1)\). The authors prove the following result. K(m,n) has a \(P_ 3\)- factorization if and only if (i) mn\(\equiv 0(mod 3)\) and (ii) (m- 1)n\(\equiv 0(mod 4)\).
0 references
spanning subgraph
0 references
edge-disjoint sum
0 references
H-factorization
0 references
complete multipartite graph
0 references
\(P_ 3\)-factorization
0 references