Orbit-counting polynomials for graphs and codes

We construct an “orbital Tutte polynomial” associated with a dual pair MM and M*M* of matrices over a principal ideal domain RR and a group GG 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 RR.In the case where MM is the signed vertex-edge incidence matrix of a graph ΓΓ over the ring of integers, the orbital Tutte polynomial specialises to count orbits of GG on proper colourings of ΓΓ or on nowhere-zero flows or tensions on ΓΓ with values in an abelian group AA. (In the case of flows, for example, we must substitute for the variable xixi the number of solutions of the equation ia=0ia=0 in the group AA. In particular, unlike the case of counting nowhere-zero flows, the answer depends on the structure of AA, not just on its order.)In the case where MM is the generator matrix of a linear code over GF(q)GF(q), the orbital Tutte polynomial specialises to count orbits of GG on words of given weight in CC or its dual.