Strong Tutte functions of matroids and graphs

Zaslavsky, Thomas

doi:10.1090/S0002-9947-1992-1080738-6

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

Signed graphs

7

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