ON THE ELUSIVENESS OF HAMILTONIAN PROPERTY

1. IntroductionA gash G is an ordered pair of disjoillt sets (V, E) such that E is a subset of the setof unordered pairs of V, where the sets V and E are finite. The set V is cajled the setof venices and E is called the set of edges. They are usually denoted by V(G) and E(C),respectively. An edge (x, y) is said to join the venices x and y, and is sometimes denotedby xo or ear. By our definition, a graph does not colltain any loOP, neither does it colltainmultiple edges.Other terms undef…

On the elusiveness of Hamiltonian property

Decision tree complexity is an important measure of computational complexity. A graph property is a set of graphs such that if some graph G is in the set then each isomorphic graph to G is also in the set. Let P be a graph property on n vertices, if every decision tree algorithm recognizing P must examine at least k pairs of vertices in the worst case, then it is said that the decision tree complexity of P is k. If every decision tree algorithm recognizing P must examine all n(n-1)/2 pairs of vertices in the worst case, then P is said to be elusive. Karp conjectured that every nontrivial monotone graph property is elusive. This paper concerns the elusiveness of Hamiltonian property. It is proved that if n=p 1, pp or pq 1, (where p,q are distinct primes), then Hamiltonian property on n vertices is elusive.