On the elusiveness of Hamiltonian property (Q5931908)

A graph property \(P\) on \(n\) vertices is a set of graphs on \(n\) vertices such that if a graph \(G\) belongs to \(P\) then any graph isomorphic to \(G\) is also in this set. Given the ability to make queries whether a desired pair of vertices of an input graph are adjacent or not, \(P\) is called elusive if it takes \(n\choose 2\) queries in the worst case to determine whether a graph \(G\) is in \(P\). In 1973 Karp conjectured that every nontrivial monotone graph property is elusive. Even though it has been verified in special cases, e.g. by \textit{J. Kahn, M. Saks} and \textit{D. Sturtevant} [Combinatorica 4, 297-306 (1984; Zbl 0577.05061)] for graphs on a prime power number of vertices, in general the conjecture still remains open. The paper under review shows that the Hamiltonian property on \(n\) vertices is elusive in case \(n=p+1\), \(pq\) or \(pq+1\) for distinct primes \(p\) and \(q\).