Tutte Invariants for Alternating Dimaps

arXiv1803.05539MaRDI QIDQ6299079FDOQ6299079

Authors: Kai Siong Yow, Graham Farr, Kerri Morgan 

Publication date: 14 March 2018

Abstract: An alternating dimap is an orientably embedded Eulerian directed graph where the edges incident with each vertex are directed inwards and outwards alternately. Three reduction operations for alternating dimaps were investigated by Farr. A minor of an alternating dimap can be obtained by reducing some of its edges using the reduction operations. Unlike classical minor operations, these reduction operations do not commute in general. A Tutte invariant for alternating dimaps is a function $P$ defined on every alternating dimap and taking values in a field such that $P$ is invariant under isomorphism and obeys a linear recurrence relation involving reduction operations. It is well known that if a graph $G$ is planar, then the Tutte polynomial $T$ satisfies $T(G;x,y)=T(G^{*};y,x)$. We note an analogous relation for the extended Tutte invariants for alternating dimaps introduced by Farr. We then characterise the Tutte invariant for alternating dimaps of genus zero under several conditions. As a result of the non-commutativity of the reduction operations, the recursions based on them cannot always be satisfied. We investigate the properties of alternating dimaps of genus zero that are required in order to obtain a well defined Tutte invariant. Some excluded minor characterisations for these alternating dimaps are also given.

This page was built for publication: Tutte Invariants for Alternating Dimaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6299079)