Geodesic
On a combinatorial search problem
Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 8-17 
E. V. Debrev. On a combinatorial search problem. Diskretnaya Matematika, Tome 14 (2002) no. 3, pp. 8-17. http://geodesic.mathdoc.fr/item/DM_2002_14_3_a1/
@article{DM_2002_14_3_a1,
     author = {E. V. Debrev},
     title = {On a combinatorial search problem},
     journal = {Diskretnaya Matematika},
     pages = {8--17},
     year = {2002},
     volume = {14},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2002_14_3_a1/}
}
TY  - JOUR
AU  - E. V. Debrev
TI  - On a combinatorial search problem
JO  - Diskretnaya Matematika
PY  - 2002
SP  - 8
EP  - 17
VL  - 14
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_2002_14_3_a1/
LA  - ru
ID  - DM_2002_14_3_a1
ER  - 
%0 Journal Article
%A E. V. Debrev
%T On a combinatorial search problem
%J Diskretnaya Matematika
%D 2002
%P 8-17
%V 14
%N 3
%U http://geodesic.mathdoc.fr/item/DM_2002_14_3_a1/
%G ru
%F DM_2002_14_3_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

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

[1] Solovev N. A., Testy (teoriya, postroenie, primenenie), Nauka, Novosibirsk, 1978 | MR

[2] Aigner M., Combinatorial search., Wiley, Berlin, 1988 | MR

[3] Ore O., Teoriya grafov, Nauka, Moskva, 1980 | MR

[4] Grebinski V., Kucherov G., “Optimal query bounds for reconstructing a Hamiltonian cycle in complete graphs”, Proc. 5th Israel Symp. Theory of Computing and Systems, IEEE Press, 1997, 166–173

[5] Grebinski V.,, Recherche combinatoire: problèmes de pesage, reconstruction de graphes et applications, Diplôme de doctorat de l'Université Henri Poincaré, 1998

[6] Ford G. W., Uhlenbeck G. E., Lectures in statistical mechanics, AMS, Providence, 1963 | MR | Zbl