Contraction–Deletion Invariants for Graphs

Authors: Bollobás B.^{1, 2}; Pebody L.¹; Riordan O.³

Source: Journal of Combinatorial Theory, Series B, Volume 80, Number 2, November 2000 , pp. 320-345(26)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

We consider generalizations of the Tutte polynomial on multigraphs obtained by keeping the main recurrence relation T(G)=T(G/e)+T(G-e) for e isin E(G) neither a bridge nor a loop and dropping the relations for bridges and loops. Our first aim is to find the universal invariant satisfying these conditions, from which all others may be obtained. Surprisingly, this turns out to be the universal V-function Z of Tutte (1947, Proc. Cambridge Philos. Soc. 43, 26–40) defined to obey the same relation for bridges as well. We also obtain a corresponding result for graphs with colours on the edges and describe the universal coloured V-function, which is more complicated than Z. Extending results of Tutte (1974, J. Combin. Theory Ser. B 16, 168–174) and Brylawski (1981, J. Combin. Theory Ser. B 30, 233–246), we give a simple proof that there are non-isomorphic graphs of arbitrarily high connectivity with the same Tutte polynomial and the same value of Z. We conjecture that almost all graphs are determined by their chromatic or Tutte polynomials and provide mild evidence to support this. Copyright 2000 Academic Press.

Keywords: Tutte polynomial; graph invariants

Language: English

Document Type: Research article

Affiliations: 1: Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee, 38152 2: Trinity College, Cambridge, CB2 1TQ, England 3: Trinity College, Cambridge, CB2 1TQ, England

Publication date: 2000-11-01