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

Jones polynomialTutte polynomialextreme coefficients

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 Tutte polynomial for signed graphs
• A convolution formula for the Tutte polynomial
• A polynomial invariant for knots via von Neumann algebras
• 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

(6)

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

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)