Graph Polynomials and Their Applications I: The Tutte Polynomial

DOI10.1007/978-0-8176-4789-6_9zbMath1221.05002arXiv0803.3079OpenAlexW2964638337MaRDI QIDQ3064401

Joanna A. Ellis-Monaghan, Criel Merino

Publication date: 21 December 2010

Published in: Structural Analysis of Complex Networks (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0803.3079

zbMATH Keywords

spanning tree chromatic polynomial Tutte polynomial flow polynomial graph polynomial reliability polynomial beta invariant Abelian sandpile model shelling polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Exact enumeration problems, generating functions (05A15) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Related Items (65)

Zonotopal algebra and forward exchange matroids ⋮ Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs ⋮ Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs ⋮ Tutte polynomials for benzenoid systems with one branched hexagon ⋮ Universal Tutte polynomial ⋮ Criterion for a graph to admit a good orientation in terms of leaf blocks ⋮ A general method for computing Tutte polynomials of self-similar graphs ⋮ A Graph Polynomial for Independent Sets of Bipartite Graphs ⋮ A Tutte Polynomial for Maps ⋮ Evaluations of Tutte polynomials of regular graphs ⋮ A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function ⋮ On the zeros of the partial Hosoya polynomial of graphs ⋮ The Tutte polynomial of an infinite family of outerplanar, small-world and self-similar graphs ⋮ Extremal graphs for the Tutte polynomial ⋮ Relations and bounds for the zeros of graph polynomials using vertex orbits ⋮ Tutte polynomial of pseudofractal scale-free web ⋮ Recipe theorem for the Tutte polynomial for matroids, renormalization group-like approach ⋮ A forest building process on simple graphs ⋮ Order quasisymmetric functions distinguish rooted trees ⋮ Interlace polynomials for multimatroids and delta-matroids ⋮ On maximum graphs in Tutte polynomial posets ⋮ Note on the subgraph component polynomial ⋮ Deletion-contraction and the surface Tutte polynomial ⋮ Topological graph polynomials in colored group field theory ⋮ Tutte and Jones polynomials of links, polyominoes and graphical recombination patterns ⋮ Graph polynomials associated with Dyson-Schwinger equations ⋮ On the activities and partitions of the vertex subsets of graphs ⋮ Measures of spin ordering in the Potts model with a generalized external magnetic field ⋮ The Tutte polynomial of a class of compound graphs and its applications ⋮ Discrimination power of graph measures based on complex zeros of the partial Hosoya polynomial ⋮ Locally free representations of quivers over commutative Frobenius algebras ⋮ Graph measures with high discrimination power revisited: a random polynomial approach ⋮ Towards detecting structural branching and cyclicity in graphs: a polynomial-based approach ⋮ Hierarchical zonotopal power ideals ⋮ A version of Tutte's polynomial for hypergraphs ⋮ The Tutte polynomial of some matroids ⋮ Upper bound for the number of spanning forests of regular graphs ⋮ Short proof of a theorem of Brylawski on the coefficients of the Tutte polynomial ⋮ Unnamed Item ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ Tutte polynomials of two self-similar network models ⋮ Binary matroids and local complementation ⋮ The zero forcing polynomial of a graph ⋮ Tutte polynomial of the Apollonian network ⋮ Encoding structural information uniquely with polynomial-based descriptors by employing the Randić matrix ⋮ Tutte polynomials and a stronger version of the Akiyama-Harary problem ⋮ Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width ⋮ A little statistical mechanics for the graph theorist ⋮ Topological graph polynomials and quantum field theory. I: Theory kernel theories ⋮ A logician's view of graph polynomials ⋮ Functional relations on anisotropic Potts models: from Biggs formula to the tetrahedron equation ⋮ A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan ⋮ Interpretations of the Tutte and characteristic polynomials of matroids ⋮ Potts model partition functions on two families of fractal lattices ⋮ The Tutte polynomial of a morphism of matroids. V: Derivatives as generating functions of Tutte activities ⋮ The behavior of Tutte polynomials of graphs under five graph operations and its applications ⋮ Tutte polynomials of vertex-weighted graphs and group cohomology ⋮ On the location of roots of graph polynomials ⋮ Semantic Equivalence of Graph Polynomials Definable in Second Order Logic ⋮ Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs ⋮ Matroids, delta-matroids and embedded graphs ⋮ Interpretations for the Tutte polynomials of morphisms of matroids ⋮ The multivariate signed Bollobás-Riordan polynomial ⋮ Flag matroids: algebra and geometry ⋮ Irreducibility of the Tutte polynomial of an embedded graph

This page was built for publication: Graph Polynomials and Their Applications I: The Tutte Polynomial