Several extreme coefficients of the Tutte polynomial of graphs

2017/05/29 by Helin Gong, Gong, Helin, Mengchen Li +3
Mathematics · #05C31 #57M27 #Advanced Combinatorial Mathematics #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology

paper · pdf · doi:10.48550/arxiv.1705.10023

openalex publication_date 2017/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let t_i,j be the coefficient of xⁱ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.

Citations

• A Contribution to the Theory of Chromatic Polynomials

Related

• Extreme coefficients of multiplicity Tutte polynomials
• Extreme coefficients of Jones polynomials and graph theory
• On maximum graphs in Tutte polynomial posets
• A Tutte polynomial for maps
• Tutte Polynomials and Related Asymptotic Limiting Functions for Recursive Families of Graphs