The vertex code

Pick an arbitrary vertex v of a vertex-transitive cubic graph. Then the distance partition with respect to v is the partition of the vertex set into cells according to the distances from v.

Now given a vertex in a cell we can classify it into one of seven types according to the cells in which its three neighbours lie. More precisely we count the number of neighbours of the vertex in the preceding cell, the same cell and the subsequent cell, and thereby assign a type to each vertex.

For example, a vertex at distance 7 from v is designated to be type 120 if it has 1 neighbour at distance 6 from v, 2 at distance 7 and 0 at distance 8. Clearly v itself always has type 003.

The vertex code simply counts the number of vertices of each type in each cell of the distance partition. Consider the following sample vertex code.

This shows us that there are 30 vertices at distance 5 from a given vertex, of which 12 are of type 102 and 18 of type 201. Notice that we can also see that the graph is bipartite as there are no vertices of type 111 or 210.