The Las Vergnas polynomial for embedded graphs

DOI10.1016/J.EJC.2015.03.009MaRDI QIDQ491745zbMATH OpenOpenAlexFDO

Authors Joanna A. Ellis-Monaghan, Iain Moffatt

Publication date 19 August 2015

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3885920 (Why is no real title available?)
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 3739583 (Why is no real title available?)
• scientific article; zbMATH DE number 3512135 (Why is no real title available?)
• scientific article; zbMATH DE number 3627205 (Why is no real title available?)
• A polynomial invariant of graphs on orientable surfaces
• A polynomial of graphs on surfaces
• A quasi-tree expansion of the Krushkal polynomial
• A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan
• Graphs on surfaces. Dualities, polynomials, and knots
• Graphs, Links, and Duality on Surfaces
• Matroids, delta-matroids and embedded graphs
• On the Tutte Polynomial of a Morphism of Matroids
• Polynomial invariants of graphs on surfaces
• The Tutte polynomial of a morphism of matroids. I: Set-pointed matroids and matroid perspectives
• The Tutte polynomial of a morphism of matroids. III: Vectorial matroids
• 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
• Twisted duality for embedded graphs

Cited in

(11)

• A Tutte polynomial for maps
• 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

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)