Bohossian, Vasken and Bruck, Jehoshua (2006) Shortening Array Codes and the Perfect 1-Factorization Conjecture. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2006.ETR075
![[img]](http://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
See Usage Policy. 148Kb |
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2006.ETR075
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.
| Item Type: | Report or Paper (Technical Report) |
|---|---|
| Group: | Parallel and Distributed Systems Group |
| Record Number: | CaltechPARADISE:2006.ETR075 |
| Persistent URL: | http://resolver.caltech.edu/CaltechPARADISE:2006.ETR075 |
| Related URLs: | |
| Usage Policy: | You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format. |
| ID Code: | 26106 |
| Collection: | CaltechPARADISE |
| Deposited By: | Imported from CaltechPARADISE |
| Deposited On: | 16 Jul 2006 |
| Last Modified: | 26 Dec 2012 13:53 |
Repository Staff Only: item control page
