Let Pk denote a path with k vertices and k - 1 edges. And let γKn,n denote the γ-fold complete bipartite graph with both parts of size n. A Pk-decomposition D of γKn,n is a family of subgraphs of γKn,n whose edge sets form a partition of the edge set of XKn-n such that each member of & is isomorphic to Pk. Necessary conditions for the existence of a Pfc-decomposition of γKn,n are (i) γn2 = 0 (mod k-1) and (ii) k ≤ n + 1 if γ = 1 and n is odd, or k ≤ 2n if A ≥ 2 or n is even. In this paper, we show these necessary conditions are sufficient except for the possibility of the case that γ = 3, n = 15, and k = 28.
|Number of pages||9|
|Publication status||Published - 2007 Oct 1|
ASJC Scopus subject areas