Several extreme coefficients of the Tutte polynomial of graphs

DOI10.1007/S00373-019-02126-YzbMATH Open1439.05111arXiv1705.10023OpenAlexW3000307408WikidataQ126383376 ScholiaQ126383376MaRDI QIDQ2175779FDOQ2175779

Authors: Helin Gong, Mengchen Li, Xianan Jin 

Publication date: 30 April 2020

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

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.

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

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

zbMATH Keywords

Jones polynomialTutte polynomialextreme coefficients

Mathematics Subject Classification ID

Graph polynomials (05C31)

Cites Work

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

Cited In (6)

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

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)