Article collection "Mathematical Problems of Cybernetics" №11, Moscow, 2002

Authors:Debrev E.V.

On identifications of graphs from some families by means of unconditioned edge tests

Abstract:

We consider undirected graphs without loops or multiple edges. Suppose that we have to identify an unknown graph X by means of a procedure that consists in choosing an edge and asking the question 'does this edge belong to the graph X?' The goal is to identify the graph X by asking as few questions as possible. The present article considers the solution of the problem above by means of unconditioned tests, i.e. algorithms which use a predefined list of edges. We study the properties of graphs corresponding to partitions of an n-vertex set into two equivalence classes; the equivalent vertices are joined by an edge and thus the equivalence classes correspond to cliques in the graph. For this family we consider the existence of an identifying graph, which in this case is to be used as an unconditioned test. We study the possible identifying graphs for various other graph families.