𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Contraction–Deletion Invariants for Graphs

✍ Scribed by Béla Bollobás; Luke Pebody; Oliver Riordan

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
192 KB
Volume
80
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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 # 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.

📜 SIMILAR VOLUMES

On graph invariants satisfying the delet
On graph invariants satisfying the deletion-contraction formula
✍ Dohmen, Klaus 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB

As a generalization of chromatic polynomials, this paper deals with real-valued mappings + on the class of graphs satisfying +(GI) = +(Gz) for all pairs GI, GZ of isomorphic graphs and +(G) = +(Ge) -rC/(G/e) for all graphs G and all edges e of G, where the definition of G/e is nonstandard. In partic

Maximum versus minimum invariants for gr
Maximum versus minimum invariants for graphs
📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 488 KB

Two examples in graph theory of the concept of the maximum and minimum pair of invariants resulting from a graphical parameter are ( I ) the chromatic number and its maximum version, the achromatic number, and (2) the genus and the maximum genus. The primary purpose of this expository survey is to p

A note on Negami's polynomial invariants
A note on Negami's polynomial invariants for graphs
✍ James G. Oxley 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 296 KB

Negami has introduced two polynomials for graphs and proved a number of properties of them. In this note, it is shown that these polynomials are intimately related to the well-known Tutte polynomial. This fact is used, together with a result of Brylawski, to answer a question of Negami. The matroid

A Ramsey property for graph invariants
A Ramsey property for graph invariants
✍ Fred Buckley 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 235 KB

## Abstract We consider the problem of which graph invariants have a certain property relating to Ramsey's theorem. Invariants which have this property are called Ramsey functions. We examine properties of chains of graphs associated with Ramsey functions. Methods are developed which enable one to