Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-28T08:53:41.989Z Has data issue: false hasContentIssue false
  • English
  • Français

A POLYNOMIAL INVARIANT OF GRAPHS ON ORIENTABLE SURFACES

Published online by Cambridge University Press:  18 October 2001

BÉLA BOLLOBÁS  and
OLIVER RIORDAN
BÉLA BOLLOBÁS
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152-6429, USA and Trinity College, Cambridge CB2 1TQ [email protected]
OLIVER RIORDAN
Affiliation:
Trinity College, Cambridge CB2 1TQ, [email protected]
Get access

Abstract

We consider cyclic graphs, that is, graphs with cyclic orders at the vertices, corresponding to 2-cell embeddings of graphs into orientable surfaces, or combinatorial maps. We construct a three variable polynomial invariant of these objects, the cyclic graph polynomial, which has many of the useful properties of the Tutte polynomial. Although the cyclic graph polynomial generalizes the Tutte polynomial, its definition is very different, and it depends on the embedding in an essential way. 2000 Mathematical Subject Classification: 05C10.

Keywords

polynomial invariantsgraph embeddings
Type
Research Article
Information
Proceedings of the London Mathematical Society , Volume 83 , Issue 3 , November 2001 , pp. 513 - 531
Copyright
2001 London Mathematical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)