The presentation of deterministic and strongly deterministic graphs

Abstract

The paper proposes a presentation of D-graphs and SD-graphs by a defining pair of words in the alphabet of their vertex labels. We present an algorithm that, given an arbitrary pair of sets, either constructs a D-graph for which this pair is the defining pair or informs that it is impossible to do so. We also present an algorithm for constructing a canonical defining pair for a D-graph and find some numerical estimates of this pair.