We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Permutation separations and complete bipartite factorizations of Kn,n.

Martin, N. and Stong, R. (2003) 'Permutation separations and complete bipartite factorizations of Kn,n.', The electronic journal of combinatorics., 10 (1). R37.


Suppose p<q are odd and relatively prime. In this paper we complete the proof that Kn,n has a factorisation into factors F whose components are copies of Kp,q if and only if n is a multiple of pq(p+q). The final step is to solve the "c-value problem" of Martin. This is accomplished by proving the following fact and some variants: For any 0≤k≤n, there exists a sequence (π1,π2,…,π2k+1) of (not necessarily distinct) permutations of {1,2,…,n} such that each value in {−k,1−k,…,k} occurs exactly n times as πj(i)−i for 1≤j≤2k−1 and 1≤i≤n.

Item Type:Article
Keywords:Permutation, Factorisation, Complete bipartite graph.
Full text:(VoR) Version of Record
Download PDF
Publisher Web site:
Record Created:29 Feb 2008
Last Modified:23 Jul 2015 14:55

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Look up in GoogleScholar | Find in a UK Library