An algorithmic classification of cubic vertex-transitive graphs

Abstract EN

We develop an algorithm for obtaining an equitable partition from any given partition of the vertices of a graph.

This idea is specialized to the case where the starting point is a partition according to the number of walks issuing from a fixed vertex.

The above ideas lead to a simple algorithm that classifies a cubic vertex – transitive graph according to the symmetry type ( s-regular, t-symmetric, or o-symmetric ).

The algorithm is tested against several types of cubic vertex-transitive graphs.

The algorithm successfully classifies all of them in their appropriate class.

The produced algorithm provides an algorithmic classification of such graphs according to their symmetry type while most of the previous methods of classification are purely theoretical