An inequality for Tutte polynomials (Q532122)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An inequality for Tutte polynomials |
scientific article |
Statements
An inequality for Tutte polynomials (English)
0 references
26 April 2011
0 references
The Tutte polynomial of the graph \(G=(V,E)\) can be defined by the closed formula \[ TG(x, y) =\sum_{A\subseteq E} (x - 1)^{r(E)-r(A)}(y - 1)^{| A| -r(A)} \] where \(r(A)=| V | -\omega (V,A)\), and \(\omega(V,A)\) denotes the number of components in the graph \((V,A)\). The author proves that, for a graph \(G\) without loops or bridges and \(a\), \(b\) positive real numbers with \(b\geq a(a+2)\), the following holds: The Tutte polynomial of \(G\) satisfies the inequality \(TG(b, 0)TG(0,b)\geq TG(a,a)^2\). This result is inspired by a conjecture of \textit{C. Merino} and \textit{D. J. A. Welsh} [``Forests, colorings and acyclic orientations of the square lattice,'' Ann. Comb. 3, No.~2--4, 417--429 (1999; Zbl 0936.05043)] which says that \(TG(1, 1)\leq \max\{TG(2, 0),TG(0, 2)\}\).
0 references
Tutte polynomial
0 references