Shortening Array Codes and the Perfect 1-Factorization Conjecture
Vasken Bohossian, Jehoshua Bruck · 2006
The existence of a perfect 1-factorization of the complete graph Kn, for arbitrary n, is a 40-year old open problem in graph theory. Two infinite families of perfect 1-factorizations are known for K2pand Kp+1, where p is a prime. It was shown in L. Xu et al. (1999) that finding a perfect 1-factorization of Kncan be reduced to a problem in coding, i.e. to constructing an MDS, lowest density array code of length n. In this paper, a new method for shortening arbitrary array codes is introduced. It is then used to derive the Kp+1family of perfect 1-factorizations from the K2pfamily, by applying the reduction mentioned above. Namely, techniques from coding theory are used to prove a new result in graph theory