✦ LIBER ✦

Tutte polynomials for trees

✍ Scribed by Sharad Chaudhary; Gary Gordon

Publisher: John Wiley and Sons
Year: 1991
Tongue: English
Weight: 682 KB
Volume: 15
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190150308

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We define two two‐variable polynomials for rooted trees and one two‐variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted trees T~1~ and T~2~ are isomorphic if and only if f(T~1~) = f(T~2~). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of size k for all k, and the number of paths of length k for all k from the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion‐contraction recursion they satisfy.

📜 SIMILAR VOLUMES

Splitting Formulas for Tutte Polynomials

✍ Artur Andrzejak 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 371 KB

We present two splitting formulas for calculating the Tutte polynomial of a matroid. The first one is for a generalized parallel connection across a 3-point line of two matroids and the second one is applicable to a 3-sum of two matroids. An important tool used is the bipointed Tutte polynomial of a

An inequality for Tutte polynomials

✍ Bill Jackson 📂 Article 📅 2010 🏛 Springer-Verlag 🌐 English ⚖ 447 KB

The Tutte polynomial

✍ Dominic Welsh 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB

This is a close approximation to the content of my lecture. After a brief survey of well known properties, I present some new interpretations relating to random graphs, lattice point enumeration, and chip firing games. I then examine complexity issues and concentrate in particular, on the existence

The Tutte polynomial

✍ Henry H. Crapo 📂 Article 📅 1969 🏛 Springer 🌐 English ⚖ 61 KB

An Interpretation for the Tutte Polynomi

An Interpretation for the Tutte Polynomial

✍ V Reiner 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 204 KB

For any matroid M realizable over Q , we give a combinatorial interpretation of the Tutte polynomial T M (x, y) which generalizes many of its known interpretations and specializations, including Tutte's coloring and flow interpretations of T M (1t, 0), T M (0, 1t); Crapo and Rota's finite field inte

A Convolution Formula for the Tutte Poly

A Convolution Formula for the Tutte Polynomial

✍ W. Kook; V. Reiner; D. Stanton 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 75 KB

Following Crapo [2], let `(x, y)(M)=x r(M) y r(M\*) , where K=Z[x, y]. Lemma 1. `(x, y) &1 =`(&x, &y).