$P_4$-Factorization of Cartesian Product of Complete Graphs

Abstract

In 1996, Muthusamy and Paulraja conjectured that for $k\ge 3$, the Cartesian product $K_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_n$ has a $P_k$-factorization if and only if $mn\equiv 0\mathrm{mod}k$ and $2(k-1)|k(m+n-2)$. Recently, Chitra and Muthusamy have partially settled this conjecture for $k=3$. In this paper, it is shown that for $k=4$ the above conjecture is true if $(m\mathrm{mod}12,n\mathrm{mod}12)$ \in $\{(0,2),(2,0),(0,8),(8,0),(2,6),(6,2),(6,8),(8,6),(4,4)\}$. The left over cases for $k=4$ are $(m\mathrm{mod}12,n\mathrm{mod}12)$\in $\{(0,5),(5,0),(0,11),(11,0),(1,4),(4,1),(3,8),(8,3),(4,7),(7,4),(4,10),(10,4),(8,9),(9,8),(10,10)\}$.