Article collection "Mathematical Problems of Cybernetics" №15, Moscow, 2006
On unconditional edge tests for regular families of graphs
We consider unconditional edge tests for undirected graphs without loops and multiple edges given on a fixed finite set of numbered vertices. For each regular family consisting of graphs with not more than two vertex similarity classes, we obtain upper and lower bounds of the minimal volume of such a test, differing not more than 8 times. Taking into account the previously obtained results, for all regular families of graphs on n numbered vertices, we find the order of n growth of the minimum volume of an unconditional edge test.