Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 24, 2006 | public
Report Open

Shortening Array Codes and the Perfect 1-Factorization Conjecture

Abstract

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 K2p and Kp+1, where p is a prime. It was shown in [8] that finding a perfect 1-factorization of Kn can 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+1 family of perfect 1-factorizations from the K2p family, by applying the reduction metioned above. Namely, techniques from coding theory are used to prove a new result in graph theory.

Files

etr075.pdf
Files (152.2 kB)
Name Size Download all
md5:b7ac48e228de75dfab4a7913b23e132b
152.2 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 24, 2023