Minors for alternating dimaps

DOI10.1093/QMATH/HAX039MaRDI QIDQ4684204zbMATH OpenOpenAlexFDO

Authors Graham Farr

Publication date 27 September 2018

Published in The Quarterly Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.2783

zbMATH Keywords

Tutte polynomial universal Tutte-like invariants for alternating dimaps

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph polynomials (05C31) Graph minors (05C83)

Abstract: We develop a theory of minors for alternating dimaps --- orientably embedded digraphs where, at each vertex, the incident edges (taken in the order given by the embedding) are directed alternately into, and out of, the vertex. We show that they are related by the triality relation of Tutte. They do not commute in general, though do in many circumstances, and we characterise the situations where they do. The relationship with triality is reminiscent of similar relationships for binary functions, due to the author, so we characterise those alternating dimaps which correspond to binary functions. We give a characterisation of alternating dimaps of at most a given genus, using a finite set of excluded minors. We also use the minor operations to define simple Tutte invariants for alternating dimaps and characterise them. We establish a connection with the Tutte polynomial, and pose the problem of characterising universal Tutte-like invariants for alternating dimaps based on these minor operations.

Recommendations

Cited in

(4)

This page was built for publication: Minors for alternating dimaps

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