The Las Vergnas polynomial for embedded graphs

DOI10.1016/J.EJC.2015.03.009zbMATH Open1319.05072arXiv1311.3762OpenAlexW2132851460MaRDI QIDQ491745FDOQ491745

Authors: Joanna A. Ellis-Monaghan, Iain Moffatt 

Publication date: 19 August 2015

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The Las Vergnas polynomial is an extension of the Tutte polynomial to cellularly embedded graphs. It was introduced by Michel Las Vergnas in 1978 as special case of his Tutte polynomial of a morphism of matroids. While the general Tutte polynomial of a morphism of matroids has a complete set of deletion-contraction relations, its specialisation to cellularly embedded graphs does not. Here we extend the Las Vergnas polynomial to graphs in pseudo-surfaces. We show that in this setting we can define deletion and contraction for embedded graphs consistently with the deletion and contraction of the underlying matroid perspective, thus yielding a version of the Las Vergnas polynomial with complete recursive definition. This also enables us to obtain a deeper understanding of the relationships among the Las Vergnas polynomial, the Bollobas-Riordan polynomial, and the Krushkal polynomial. We also take this opportunity to extend some of Las Vergnas' results on Eulerian circuits from graphs in surfaces of low genus to surfaces of arbitrary genus.

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

Recommendations

• Types of embedded graphs and their Tutte polynomials
• Topological extensions of the Tutte polynomial
• A quasi-tree expansion of the Krushkal polynomial
• A Tutte polynomial for maps. II: The non-orientable case
• A Tutte polynomial for maps

zbMATH Keywords

Tutte polynomialKrushkal polynomialBollobás-Riordan polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• The Tutte polynomial of a morphism of matroids. I: Set-pointed matroids and matroid perspectives
• Title not available (Why is that?)
• On the Tutte Polynomial of a Morphism of Matroids
• Title not available (Why is that?)
• Title not available (Why is that?)
• A polynomial invariant of graphs on orientable surfaces
• Graphs on surfaces. Dualities, polynomials, and knots
• A polynomial of graphs on surfaces
• A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan
• Matroids, delta-matroids and embedded graphs
• Twisted duality for embedded graphs
• Graphs, Links, and Duality on Surfaces
• The Tutte polynomial of a morphism of matroids. III: Vectorial matroids
• Polynomial invariants of graphs on surfaces
• The Tutte polynomial of a morphism of matroids. IV: Computational complexity
• The Tutte polynomial of a morphism of matroids. V: Derivatives as generating functions of Tutte activities
• Title not available (Why is that?)
• Title not available (Why is that?)
• A quasi-tree expansion of the Krushkal polynomial

Cited In (11)

• Logarithmic concavity for morphisms of matroids
• On the activities of \(p\)-basis of matroid perspectives
• Edge colourings and topological graph polynomials
• Cyclic flats and corners of the linking polynomial
• Hopf algebras and Tutte polynomials
• Matroids arising from electrical networks
• Matroidal frameworks for topological Tutte polynomials
• Types of embedded graphs and their Tutte polynomials
• A quasi-tree expansion of the Krushkal polynomial
• Deletion-contraction and the surface Tutte polynomial
• A Tutte polynomial for maps

This page was built for publication: The Las Vergnas polynomial for embedded graphs

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