Path decompositions of γKn,n

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)211-219
Number of pages9
JournalArs Combinatoria
Volume85
Publication statusPublished - 2007 Oct 1
Externally publishedYes

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Path decompositions of γK<sub>n,n</sub>'. Together they form a unique fingerprint.

  • Cite this