Introduction and definitions

We can instal a graph G of order n into a computer by encoding the entries of the upper triangular part of its adjacency matrix. One problem arises naturally : “Can we find, in the worst case, whether the graph G has a specific property P, without decoding all the n(n–1)/2 entries of the upper triangular part of its adjacency matrix?”

The main objective of this chapter is to introduce a Two Person Game to tackle the above problem.

Let Gn be the set of all graphs of order n and let F ⊆. Gn be the set of all graphs such that each of its members has property P. To see that whether a graph G (of order n) possesses property P or not, it is equivalent of showing whether G belongs to F or not. Hence we can introduce the Two Person Game in a general setting and treat the graph property as a special case.

Let T be a finite set of cardinality |T| = t and let p(T) be the power set of T, i.e. the set of all subsets of T. We call F ⊆ p(T) a property of T. A measure of the minimum amount of information necessary, in the worst case, to determine membership of F is as follows. Suppose two players, called the Constructor (Hider) and Algy (Seeker), play the following game which we also denote by F. Algy asks questions of the Constructor about a hypothetical set H ⊂ T.