Graphs, which orbits contain no more than three vertices

Abstract

We consider the improved algorithm Vizing - Nazarets and study the applicability of this polynomial algorithm to the partition of the vertices of ordinary graphs on orbit. For this purpose the r-strictly similar and the strictly similar vertices and the sets of vertices are defined and their properties are studied. It is proved that any orbit of the graph is completely contained in one of the classes of strictly similar vertices. On the other hand, it is proved that if the classes of strict equivalence consist of no more than three vertices, then these same classes are orbits