Graph Polynomials and Their Applications I: The Tutte Polynomial

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

Chapter Chapter 9 in Structural Analysis of Complex Networks, 2011, pp 219-255 from Springer

Abstract: Abstract In this survey of graph polynomials, we emphasize the Tutte polynomial and a selection of closely related graph polynomials such as the chromatic, flow, reliability, and shelling polynomials. We explore some of the Tutte polynomial’s many properties and applications and we use the Tutte polynomial to showcase a variety of principles and techniques for graph polynomials in general. These include several ways in which a graph polynomial may be defined and methods for extracting combinatorial information and algebraic properties from a graph polynomial. We also use the Tutte polynomial to demonstrate how graph polynomials may be both specialized and generalized, and how they can encode information relevant to physical applications. We conclude with a brief discussion of computational complexity considerations.

Keywords: Tutte polynomial; Graph polynomial; Chromatic polynomial; Flow polynomial; Reliability polynomial; Shelling polynomial; Abelian sandpile model; Spanning tree; Beta invariant (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_9

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

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

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 ().