On a combinatorial search problem

In this paper, we consider the problem of searching for undirected Hamiltonian circuits in the complete graph on $n$ vertices with the use of unconditional edge tests. We prove that the minimal test contains exactly $n(n-3)/2-\lfloor n/3\rfloor+1$ edges. We propose an explicit characterisation of all minimal difference sets of edges.
This research was supported by the Russian Foundation for Basic Research, grants 02–01–00985 and 00-15–96103, by the Program ‘Universities of Russia,’ and the Federal Program ‘Integration.’