Several extreme coefficients of the Tutte polynomial of graphs

DOI10.1007/S00373-019-02126-YMaRDI QIDQ2175779zbMATH OpenOpenAlexWikidataFDO

Authors Helin Gong, Mengchen Li, Xianan Jin

Publication date 30 April 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.10023

zbMATH Keywords

extreme coefficientsJones polynomialTutte polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31)

Abstract: Let $t_{i,j}$ be the coefficient of $x^i{y}^j$ in the Tutte polynomial $T(G;x,y)$ of a connected bridgeless and loopless graph $G$ with order $n$ and size $m$. It is trivial that $t_{0,m-n+1}=1$ and $t_{n-1,0}=1$. In this paper, we obtain expressions of another eight extreme coefficients $t_{i,j}$'s with $(i,j)=(0,m-n)$,$(0,m-n-1)$,$(n-2,0)$,$(n-3,0)$,$(1,m-n)$,$(1,m-n-1)$,$(n-2,1)$ and $(n-3,1)$ in terms of small substructures of $G$. Among them, the former four can be obtained by using coefficients of the highest, second highest and third highest terms of chromatic or flow polynomials, and vice versa. We also discuss their duality property and their specializations to extreme coefficients of the Jones polynomial.

Recommendations

• On coefficients of the Tutte polynomial
• Extreme coefficients of Jones polynomials and graph theory
• Essential properties of the Tutte polynomial
• Rank and Bollobás-Riordan polynomials: Coefficient measures and zeros
• The complexities of the coefficients of the Tutte polynomial

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• A convolution formula for the Tutte polynomial
• A polynomial invariant for knots via von Neumann algebras
• A Tutte polynomial for signed graphs
• A volumish theorem for the Jones polynomial of alternating knots
• An introduction to chromatic polynomials
• Coefficients of chromatic polynomials
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Zeros of Jones polynomials of graphs

Cited in

(7)

• The coefficients of the Tutte polynomial are not unimodal
• Tutte polynomials and related asymptotic limiting functions for recursive families of graphs
• On coefficients of the Tutte polynomial
• Extremal graphs for the Tutte polynomial
• On maximum graphs in Tutte polynomial posets
• Coefficients of the Tutte polynomial and minimal edge cuts of a graph
• Bounds for the coefficients of flow polynomials

This page was built for publication: Several extreme coefficients of the Tutte polynomial of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175779)