An inequality for Tutte polynomials (Q532122)

From MaRDI portal
Revision as of 23:29, 3 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)





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