Graph Polynomials and Their Applications II: Interrelations and Interpretations

Joanna A. Ellis-Monaghan () and Criel Merino
Additional contact information
Joanna A. Ellis-Monaghan: Saint Michaels College, Department of Mathematics

Chapter Chapter 10 in Structural Analysis of Complex Networks, 2011, pp 257-292 from Springer

Abstract: Abstract We survey a variety of graph polynomials, giving a brief overview of techniques for defining a graph polynomial and then for decoding the combinatorial information it contains. These polynomials are not generally specializations of the Tutte polynomial, but they are each in some way related to the Tutte polynomial, and often to one another. We emphasize these interrelations and explore how an understanding of one polynomial can guide research into others. We also discuss multivariable generalizations of some of these polynomials and the theory facilitated by this. We conclude with two examples, the interlace polynomial in biology and the Tutte polynomial and Potts model in physics, that illustrate the applicability of graph polynomials in other fields.

Keywords: Tutte polynomial; Characteristic polynomial; Matching polynomial; Penrose polynomial; Martin polynomial; Circuit partition polynomial; Ehrhart polynomial; Interlace polynomial; U-polynomial; W-polynomial; Bollobás–Riordan polynomial; Ribbon graph polynomial; Topological Tutte polynomial; Multivariable Tutte polynomial; Parametrized Tutte polynomial; Transition polynomial; Polychromate; Symmetric function; DNA sequencing; Potts model (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-8176-4789-6_10

Ordering information: This item can be ordered from
http://www.springer.com/9780817647896

DOI: 10.1007/978-0-8176-4789-6_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().