Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Strong Tutte functions of matroids and graphs


Author: Thomas Zaslavsky
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Thomas A. Brylawski, A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235-282. MR 46 #8869. MR 0309764 (46:8869)
  • [2] Henry H. Crapo, The Tutte polynomial, Aequationes Math. 3 (1969), 211-229. MR 41 #6705. MR 0262095 (41:6705)
  • [3] 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 0359655 (50:12107)
  • [4] Louis H. Kauffman, Signed graphs, Abstracts Amer. Math. Soc. 7 (1986), 307, Abstract 828-57-12.
  • [5] -, New invariants in the theory of knots, Amer. Math. Monthly 95 (1988), 195-242. MR 89d:57005. MR 935433 (89d:57005)
  • [6] -, A Tutte polynomial for signed graphs, Discrete Appl. Math. 25 (1989), 105-127. MR 91c:05082. MR 1031266 (91c:05082)
  • [7] Kunio Murasugi, On invariants of graphs with applications to knot theory, Trans. Amer. Math. Soc. 314 (1989), 1-49. MR 930077 (89k:57016)
  • [8] James Oxley, Graphs and series-parallel networks, Chapter 6 in [13, pp. 97-126]. MR 849395
  • [9] Morwen B. Thistlethwaite, A spanning tree expansion of the Jones polynomial, Topology 26 (1987), 297-309. MR 899051 (88h:57007)
  • [10] Lorenzo Traldi, A dichromatic polynomial for weighted graphs and link polynomials, Proc. Amer. Math. Soc. 106 (1989), 279-286, MR 955462 (90a:57013)
  • [11] W. T. Tutte, A ring in graph theory, Proc. Cambridge Philos. Soc. 43 (1947), 26-40. MR 8, 234. Reprinted with commentary in Selected Papers of W. T. Tutte (D. McCarthy and R. G. Stanton, eds.), vol. I, Charles Babbage Research Centre, St. Pierre, Manitoba, Canada, 1979, pp. 51-69. MR 0018406 (8:284k)
  • [12] W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80-91. MR 15, 814. Reprinted with commentary in Selected Papers of W. T. Tutte (D. McCarthy and R. G. Stanton, eds.), vol. I, Charles Babbage Research Centre, St. Pierre, Manitoba, Canada, 1979, pp. 153-168. MR 0061366 (15:814c)
  • [13] Neil White, ed., Theory of matroids, Encyclopedia Math. Appl., vol. 26, Cambridge Univ. Press, Cambridge, 1986. MR 87k: 05054. MR 849389 (87k:05054)
  • [14] H. Whitney, $ 2$-isomorphic graphs, Amer. J. Math. 55 (1933), 245-254. MR 1506961

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05B35, 05C99, 57M25

Retrieve articles in all journals with MSC: 05B35, 05C99, 57M25


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1992-1080738-6
Keywords: Tutte function, Tutte-Grothendieck invariant, signed graph, rank polynomial, dichromatic polynomial, link diagram, Kauffman polynomial
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society