\(P_ 3\)-factorization of complete bipartite graphs
type: Item
instance of: scholarly article
title: \(P_ 3\)-factorization of complete bipartite graphs
zbMATH Open document ID: 0667.05045
DOI: 10.1016/0012-365X(88)90227-0
author: Kazuhiko Ushio
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: Let \(P_ 3\) be a path of 3 points and \(K_{m,n}\) be a complete bipartite graph with partite sets \(V_ 1\) and \(V_ 2\), where \(| V_ 1| =m\) and \(| V_ 2| =n.\) A spanning subgraph F of \(K_{m,n}\) is called a \(P_ 3\)-factor if each component of F is isomorphic to \(P_ 3\). If \(K_{m,n}\) is expressed as a line-disjoint sum of \(P_ 3\)-factors, then this sum is called a \(P_ 3\)-factorization of \(K_{m,n}.\) In this paper, it is shown that a necessary and sufficient condition for the existence of a \(P_ 3\)-factorization of \(K_{m,n}\) is (i) \(m+n\equiv 0\) (mod 3), (ii) \(m\leq 2n\), (iii) \(n\leq 2m\) and (iv) \(3mn/2(m+n)\) is an integer.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4091553
zbMATH Keywords: path-factorization
zbMATH Keywords: path-factor
zbMATH Keywords: complete bipartite graph
zbMATH Keywords: \(P_ 3\)- factors
zbMATH Keywords: \(P_ 3\)-factorization
MaRDI profile type: Publication
cites work: Q3818315
cites work: Parallel concepts in graph theory
description: scientific article; zbMATH DE number 4091553