Abstract
We generalize Brylawski’s formula of the Tutte polynomial of a tensor product of matroids to colored connected graphs, matroids, and disconnected graphs. Unlike the non-colored tensor product where all edges have to be replaced by the same graph, our colored generalization of the tensor product operation allows individual edge replacement. The colored Tutte polynomials we compute exists by the results of Bollobás and Riordan. The proof depends on finding the correct generalization of the two components of the pointed Tutte polynomial, first studied by Brylawski and Oxley, and on careful enumeration of the connected components in a tensor product. Our results make the calculation of certain invariants of many composite networks easier, provided that the invariants are obtained from the colored Tutte polynomials via substitution and the composite networks are represented as tensor products of colored graphs. In particular, our method can be used to calculate (with relative ease) the expected number of connected components after an accident hits a composite network in which some major links are identical subnetworks in themselves.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bollobás, B., Riordan, O.: A Tutte polynomial for coloured graphs. Combin. Prob. Comput. 8, 45–93 (1999)
Bruns, W., Wetter, U.: Determinantal Rings. Springer Lecture Notes in Mathematics # 1327., Berlin-Heidelberg: Springer-Verlag (1988)
Brylawski, T.: The Tutte polynomial I: general theory. In: Matroid Theory and its Applications. Barlotti, A. (ed.), Liguori Editore, S.r.I, pp. 125–275 (1982)
Brylawski, T., Oxley, J.: The Tutte polynomial and its applications, Matroid Applications. In: White, N. (ed.), pp. 123–225. Cambridge University Press, Cambridge (1992)
Diao, Y., Ernst, C., Ziegler, U.: Jones polynomial of knots formed by repeated tangle replacement operations. Available at http://www.math.uncc.edu/files/preprint/2008/2008_03.pdf. (preprint)
Diao, Y., Hetyei, G., Hinson, K.: Tutte polynomials of tensor products of signed graphs and their applications in knot theory. J. Knot Theory Ramif. (to appear)
Fortuin, C.M., Kasteleyn, P.W.: On the random-cluster model I. Introduction and Relation to Other Models. Physica 57, 536–564 (1972)
Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108, 35–53 (1990)
Kauffman, L.H.: New invariants in the theory of knots. Amer. Math. Mon. 95(3), 195–242 (1988)
Kauffman, L.H.: A Tutte polynomial for signed graphs. Discrete Appl. Math. 25, 105–127 (1989)
Tutte, W.T.: A contribution to the theory of chromatic polynomials. Can. J. Math. 6, 80–91 (1954)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Diao, Y., Hetyei, G. & Hinson, K. Invariants of Composite Networks Arising as a Tensor Product. Graphs and Combinatorics 25, 273–290 (2009). https://doi.org/10.1007/s00373-009-0849-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-009-0849-5