Exploring the Tutte–Martin connection

AbstractThe Martin polynomial of an oriented Eulerian graph encodes information about families of cycles in the graph. This paper uses a transformation of the Martin polynomial that facilitates standard combinatorial manipulations. These manipulations result in several new identities for the Martin polynomial, including a differentiation formula. These identities are then applied to get new combinatorial interpretations for valuations of the Martin polynomial, revealing properties of oriented Eulerian graphs. Furthermore, Martin (Thesis, Grenoble, 1977; J. Combin. Theory, Ser. B 24 (1978) 318) and Las Vergnas (Graph Theory and Combinatorics, Research Notes in Mathematics, Vol. 34, Pitman, Boston, 1979; J. Combin. Theory, Ser. B 44 (1988) 367), discovered that if Gm, the medial graph of a connected planar graph G, is given an appropriate orientation, then m(G→m;x)=t(G;x,x), where m(G→;x) is the Martin polynomial of an oriented graph, and t(G;x,y) is the Tutte, or dichromatic, polynomial. This relationship, combined with the new evaluations of the Martin polynomial, reveals some surprising properties of the Tutte polynomial of a planar graph along the diagonal x=y. For small values of x and y that correspond to points where interpretations of the Tutte polynomial are known, this leads to some interesting combinatorial identities, including a new interpretation for the beta invariant of a planar graph. Combinatorial interpretations for some values of the derivatives of t(G;x,x) for a planar graph G are also found