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