Bipartite variation of the cheesecake factory problem: mH(k,2l+1)mH(k,2l+1)-factorization of Kn,nKn,n

For k≥2l+1≥3k≥2l+1≥3, let H(k,2l+1)H(k,2l+1) be a bipartite graph with bipartition X={x1,x2,…,xk}, Y={y1,y2,…,yk} and edge set {xiyi±j∣1≤i±j≤k,i=1,2,…,k;j=0,1,2,…,l}. In 2009, Dalibor Froncek raised the Rectangular Table Negotiation Problem: In graph theoretical terms it is equivalent to finding an mH(k,2l+1)mH(k,2l+1)-factorization of Kn,nKn,n, where n=mkn=mk. Also he answered the above problem for H(k,3)H(k,3) when kk is odd and left open the remaining cases. In this paper, we show that the necessary conditions n=mkn=mk and m≡0(modε(k,l)d), where ε(k,l)=k(2l+1)−l(l+1)ε(k,l)=k(2l+1)−l(l+1) = the number of edges in H(k,2l+1)H(k,2l+1) and d=gcd(k2,ε(k,l))d=gcd(k2,ε(k,l)) for the existence of mH(k,2l+1)mH(k,2l+1)-factorization of Kn,nKn,n are also sufficient when d=1,2d=1,2, l,orl+1≡0(modd). In fact our results partially answer the Rectangular Table Negotiation Problem and also deduce the result of Froncek as a corollary.