Published May 24, 2006
| public
Report
Open
Shortening Array Codes and the Perfect 1-Factorization Conjecture
- Creators
- Bohossian, Vasken
- Bruck, Jehoshua
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
- Eprint ID
- 26106
- Resolver ID
- CaltechPARADISE:2006.ETR075
- Created
-
2006-07-16Created from EPrint's datestamp field
- Updated
-
2019-11-22Created from EPrint's last_modified field
- Caltech groups
- Parallel and Distributed Systems Group