Abstract
An isomorphism certificate of a labeled tournament T is a labeled subdigraph of T which together with an unlabeled copy of T allows the errorless reconstruction of T. It is shown that any tournament on n vertices contains an isomorphism certificate with at most n log2 n edges. This answers a question of Fishburn, Kim and Tetali. A score certificate of T is a labeled subdigraph of T which together with the score sequence of T allows its errorless reconstruction. It is shown that there is an absolute constant ∈ > 0 so that any tournament on n vertices contains a score certificate with at most (1/2 - ∈)n2 edges.
| Original language | English (US) |
|---|---|
| Pages (from-to) | XXIX-XXX |
| Journal | Electronic Journal of Combinatorics |
| Volume | 4 |
| Issue number | 1 |
| State | Published - 1997 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics