Shortening Array Codes and the Perfect 1-Factorization Conjecture

Bohossian, Vasken and Bruck, Jehoshua (2006) Shortening Array Codes and the Perfect 1-Factorization Conjecture. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2006.ETR075]

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

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.

EPrint Type:	Monograph (Technical Report)
Additional Information:	Also available online: http://www.paradise.caltech.edu/papers/etr075.pdf
Subjects:	All Records
ID Code:	103
Deposited By:	Caltech Library System
Deposited On:	16 July 2006
Record Number:	CaltechPARADISE:2006.ETR075
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:2006.ETR075
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record