This article is cited in 2 papers

On a combinatorial search problem

E. V. Debrev


Abstract: 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.’

UDC: 519.6

Received: 24.05.2002

DOI: 10.4213/dm249

 English version: Discrete Mathematics and Applications, 2002, 12:4, 325–335

Bibliographic databases:

• 
•