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.
DIMACS Home Page