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
    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
    0 references
    Tutte polynomial
    0 references

    Identifiers