Combinatorics, Probability and Computing

Paper

The Tutte Polynomial Characterizes Simple Outerplanar Graphs

A. J. GOODALLa1, A. de MIERa2, S. D. NOBLEa3 and M. NOYa2

a1 Department of Applied Mathematics and Institute of Theoretical Computer Science, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic (e-mail: goodall.aj@googlemail.com)

a2 Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1-3, 08034 Barcelona, Spain (e-mail: anna.de.mier@upc.edu, marc.noy@upc.edu)

a3 Department of Mathematical Sciences, Brunel University, Kingston Lane, Uxbridge UB8 3PH, UK (e-mail: steven.noble@brunel.ac.uk)

Abstract

We show that if G is a simple outerplanar graph and H is a graph with the same Tutte polynomial as G, then H is also outerplanar. Examples show that the condition of G being simple cannot be omitted.

(Received May 27 2010)

(Revised February 02 2011)

(Online publication March 09 2011)