### Abstract

Let P_{k} denote a path with k vertices and k - 1 edges. And let γK_{n,n} denote the γ-fold complete bipartite graph with both parts of size n. A P_{k}-decomposition D of γK_{n,n} is a family of subgraphs of γK_{n,n} whose edge sets form a partition of the edge set of XKn-n such that each member of & is isomorphic to P_{k}. Necessary conditions for the existence of a Pfc-decomposition of γK_{n,n} are (i) γn^{2} = 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.

Original language | English |
---|---|

Pages (from-to) | 211-219 |

Number of pages | 9 |

Journal | Ars Combinatoria |

Volume | 85 |

Publication status | Published - 2007 Oct 1 |

Externally published | Yes |

### Fingerprint

### ASJC Scopus subject areas

- Mathematics(all)