Name
Abstract | ||
|---|---|---|
An isomorphism certicate of a labeled tournament T is a labeled subdigraph of T which to- gether with an unlabeled copy of T allows the errorless reconstruction of T. It is shown that any tournament on n vertices contains an isomorphism certicate with at most n log2n edges. This answers a question of Fishburn, Kim and Tetali. A score certicate 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 certicate with at most (1=2 )n2 edges. |
Year | Venue | Field |
|---|---|---|
1997 | Journal of Graph Theory | Discrete mathematics,Tournament,Combinatorics,Vertex (geometry),Isomorphism,Mathematics,Certificate |
DocType | Volume | Issue |
Journal | 4 | 1 |
Citations | PageRank | References |
5 | 0.65 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| M. Ruszinkó | 2 | 230 | 35.16 |