Orbit-counting polynomials for graphs and codes

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