1992/11/01 by Thomas Zasĺavsky · 2 citations
Computer Science · Engineering · Mathematics · #Computability, Logic, AI Algorithms #Advanced Algebra and Logic #graph theory and CDMA systems #Matroid #Mathematics #Combinatorics #Tutte polynomial #Discrete mathematics #Graph #Line graph
paper · doi:10.2307/2153985
openalex publication_date 1992/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
A strong Tutte function of matroids is a function of finite matroids which satisfies F(M1 ⊕ M2) = F(M1)F(M2) and F(M) = aeF(M\backslash e) + beF(M/e) for e not a loop or coloop of M, where ae, be are scalar parameters depending only on e. We classify strong Tutte functions of all matroids into seven types, generalizing Brylawskiâs classification of Tutte-Grothendieck invariants. One type is, like Tutte-Grothendieck invariants, an evaluation of a rank polynomial; all types are given by a Tutte polynomial. The classification remains valid if the domain is any minor-closed class of matroids containing all three-point matroids. Similar classifications hold for strong Tutte functions of colored matroids, where the parameters depend on the color of e, and for strong Tutte functions of graphs and edge-colored graphs whose values do not depend on the attachments of loops. The latter classification implies new characterizations of Kauffmanâs bracket polynomials of signed graphs and link diagrams.