## Strong Tutte functions of matroids and graphs

HTML articles powered by AMS MathViewer

- by Thomas Zaslavsky PDF
- Trans. Amer. Math. Soc.
**334**(1992), 317-347 Request permission

## Abstract:

A strong Tutte function of matroids is a function of finite matroids which satisfies $F({M_1} \oplus {M_2}) = F({M_1})F({M_2})$ and $F(M) = {a_e}F(M\backslash e) + {b_e}F(M/e)$ for $e$ not a loop or coloop of $M$, where ${a_e}$, ${b_e}$ 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.## References

- Thomas H. Brylawski,
*A decomposition for combinatorial geometries*, Trans. Amer. Math. Soc.**171**(1972), 235–282. MR**309764**, DOI 10.1090/S0002-9947-1972-0309764-6 - Henry H. Crapo,
*The Tutte polynomial*, Aequationes Math.**3**(1969), 211–229. MR**262095**, DOI 10.1007/BF01817442 - C. M. Fortuin and P. W. Kasteleyn,
*On the random-cluster model. I. Introduction and relation to other models*, Physica**57**(1972), 536–564. MR**359655**
Louis H. Kauffman, - Louis H. Kauffman,
*New invariants in the theory of knots*, Amer. Math. Monthly**95**(1988), no. 3, 195–242. MR**935433**, DOI 10.2307/2323625 - Louis H. Kauffman,
*A Tutte polynomial for signed graphs*, Discrete Appl. Math.**25**(1989), no. 1-2, 105–127. Combinatorics and complexity (Chicago, IL, 1987). MR**1031266**, DOI 10.1016/0166-218X(89)90049-8 - Kunio Murasugi,
*On invariants of graphs with applications to knot theory*, Trans. Amer. Math. Soc.**314**(1989), no. 1, 1–49. MR**930077**, DOI 10.1090/S0002-9947-1989-0930077-6 - James Oxley,
*Graphs and series-parallel networks*, Theory of matroids, Encyclopedia Math. Appl., vol. 26, Cambridge Univ. Press, Cambridge, 1986, pp. 97–126. MR**849395**, DOI 10.1017/CBO9780511629563.009 - Morwen B. Thistlethwaite,
*A spanning tree expansion of the Jones polynomial*, Topology**26**(1987), no. 3, 297–309. MR**899051**, DOI 10.1016/0040-9383(87)90003-6 - Lorenzo Traldi,
*A dichromatic polynomial for weighted graphs and link polynomials*, Proc. Amer. Math. Soc.**106**(1989), no. 1, 279–286. MR**955462**, DOI 10.1090/S0002-9939-1989-0955462-3 - W. T. Tutte,
*A ring in graph theory*, Proc. Cambridge Philos. Soc.**43**(1947), 26–40. MR**18406**, DOI 10.1017/s0305004100023173 - W. T. Tutte,
*A contribution to the theory of chromatic polynomials*, Canad. J. Math.**6**(1954), 80–91. MR**61366**, DOI 10.4153/cjm-1954-010-9 - Neil White (ed.),
*Theory of matroids*, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge University Press, Cambridge, 1986. MR**849389**, DOI 10.1017/CBO9780511629563 - Hassler Whitney,
*2-Isomorphic Graphs*, Amer. J. Math.**55**(1933), no. 1-4, 245–254. MR**1506961**, DOI 10.2307/2371127

*Signed graphs*, Abstracts Amer. Math. Soc.

**7**(1986), 307, Abstract 828-57-12.

## Additional Information

- © Copyright 1992 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**334**(1992), 317-347 - MSC: Primary 05B35; Secondary 05C99, 57M25
- DOI: https://doi.org/10.1090/S0002-9947-1992-1080738-6
- MathSciNet review: 1080738