Orbit-counting polynomials for graphs and codes Original Research Article

We construct an “orbital Tutte polynomial” associated with a dual pair image and image of matrices over a principal ideal domain image and a group image of automorphisms of the row spaces of the matrices. The polynomial has two sequences of variables, each sequence indexed by associate classes of elements of image. In the case where image is the signed vertex-edge incidence matrix of a graph image over the ring of integers, the orbital Tutte polynomial specialises to count orbits of image on proper colourings of image or on nowhere-zero flows or tensions on image with values in an abelian group image. (In the case of flows, for example, we must substitute for the variable image the number of solutions of the equation image in the group image. In particular, unlike the case of counting nowhere-zero flows, the answer depends on the structure of image, not just on its order.) In the case where image is the generator matrix of a linear code over image, the orbital Tutte polynomial specialises to count orbits of image on words of given weight in image or its dual.