## DIMACS TR: 94-06

## Tournament Certificates

### Authors: Peter Fishburn, Jeong Han Kim, Prasad Tetali

**
ABSTRACT
**

A tournament certificate is a subdigraph of a labeled tournament T that in
conjunction with unlabeled information I about T allows errorless
reconstruction of T. The paper examines isomorphism certificates, where I
is an unlabeled copy of T, and score certificates, where I is T's score
sequence. We focus on aspects of edge-minimum certificates.
The work was motivated by Ariel Rubenstein's conjecture for isomorphism
certificates that, with a few noted exceptions, every such certificate for an
n-vertex tournament has at least n-1 edges. We resolve this only for
n < 7, but prove elsewhere that the similar conjecture for score
certificates is true. The paper also investigates maximum edge-minimum
certificates for all n-vertex tournaments.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-06.ps

DIMACS Home Page