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