The magnitude of a graph
Author:
Open Access
- 27 November 2017
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society
- Vol. 166 (2) , 247-264
Abstract
The magnitude of a graph is one of a family of cardinality-like invariants extending across mathematics; it is a cousin to Euler characteristic and geometric measure. Among its cardinality-like properties are multiplicativity with respect to cartesian product and an inclusion-exclusion formula for the magnitude of a union. Formally, the magnitude of a graph is both a rational function over ℚ and a power series over ℤ. It shares features with one of the most important of all graph invariants, the Tutte polynomial; for instance, magnitude is invariant under Whitney twists when the points of identification are adjacent. Nevertheless, the magnitude of a graph is not determined by its Tutte polynomial, nor even by its cycle matroid, and it therefore carries information that they do not.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Maximizing Diversity in Biology and BeyondEntropy, 2016
- Magnitude, Diversity, Capacities, and Dimensions of Metric SpacesPotential Analysis, 2014
- Positive definite metric spacesPositivity, 2012
- On the asymptotic magnitude of subsets of Euclidean spaceGeometriae Dedicata, 2012
- Algebraic Graph Theory2001
- A categorification of the Jones polynomialDuke Mathematical Journal, 2000
- Negative sets have Euler characteristic and dimension1991
- On the foundations of combinatorial theory I. Theory of M bius FunctionsProbability Theory and Related Fields, 1964
- A Contribution to the Theory of Chromatic PolynomialsCanadian Journal of Mathematics, 1954
- 2-Isomorphic GraphsAmerican Journal of Mathematics, 1933