Graph polynomials and their applications. II: Interrelations and interpretations

DOI10.1007/978-0-8176-4789-6_10MaRDI QIDQ3064402zbMATH OpenOpenAlexFDO

Authors 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/0806.4699

zbMATH Keywords

Bollobás-Riordan polynomialcharacteristic polynomialcircuit partition polynomialDNA sequencingEhrhart polynomialinterlace polynomialMartin polynomialmatching polynomialmultivariable Tutte polynomialparametrized Tutte polynomialPenrose polynomialpolychromatePotts modelRibbon graph polynomialsymmetric functiontopological tutte polynomialtransition polynomialTutte polynomialU-polynomialW-polynomial

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph polynomials (05C31) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory (05C90) Symmetric functions and generalizations (05E05)

Abstract: This paper surveys a comprehensive, although not exhaustive, sampling of graph polynomials with the goal of providing a brief overview of a variety of techniques defining a graph polynomial and then for decoding the combinatorial information it contains. The polynomials we discuss here 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, one from biology and one from physics, that illustrate the applicability of graph polynomials in other fields. This is the second chapter of a two chapter series, and concludes Graph Polynomials and Their Applications I: The Tutte Polynomial, arXiv:0803.3079

Recommendations

• Graph polynomials and their applications. I: The Tutte polynomial
• Graph polynomials
• The interlace polynomial of a graph
• The interlace polynomial and the Tutte–Martin polynomial
• Handbook of the Tutte polynomial and related topics

Cited in

(43)

• The multivariate signed Bollobás-Riordan polynomial
• A forest building process on simple graphs
• Order quasisymmetric functions distinguish rooted trees
• The zero forcing polynomial of a graph
• Orientations, lattice polytopes, and group arrangements. III: Cartesian product arrangements and applications to Tutte type polynomials
• A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan
• Graph polynomials
• A graph polynomial for independent sets of bipartite graphs
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Graph polynomials and their applications. I: The Tutte polynomial
• scientific article; zbMATH DE number 3882488 (Why is no real title available?)
• scientific article; zbMATH DE number 3841912 (Why is no real title available?)
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Interlace polynomials for multimatroids and delta-matroids
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• Some new topological indices of silicate network via M-polynomial
• Acyclic polynomials of graphs
• Handbook of the Tutte polynomial and related topics
• scientific article; zbMATH DE number 7200914 (Why is no real title available?)
• scientific article; zbMATH DE number 3893227 (Why is no real title available?)
• Evaluations of Graph Polynomials
• Skein polynomials and the Tutte polynomial when x = y
• Logical Approaches to Computational Barriers
• CONNECTED COMMON NEIGHBORHOOD SYSTEMS OF CLIQUES IN A GRAPH: A POLYNOMIAL REPRESENTATION
• CONNECTED TOTAL DOMINATING NEIGHBORHOOD POLYNOMIAL OF GRAPHS
• Graph polynomials associated with Dyson-Schwinger equations
• POLYNOMIAL REPRESENTATIONS OF THE BICLIQUE NEIGHBORHOOD OF GRAPHS
• FROM GRAPHS TO POLYNOMIAL RINGS: STAR POLYNOMIAL REPRESENTATION OF GRAPHS
• CONVEX INDEPENDENT COMMON NEIGHBORHOOD POLYNOMIAL OF A GRAPH
• COMBINATORIAL APPROACH FOR COUNTING GEODETIC SETS WITH SUBDOMINATING NEIGHBORHOOD SYSTEMS
• CONNECTED DOMINATING INDEPENDENT NEIGHBORHOOD POLYNOMIAL OF GRAPHS
• INDUCED PATH POLYNOMIAL OF GRAPHS
• Topological graph polynomials in colored group field theory
• Polynomial representation of the neighborhood systems of cliques in the Corona of graphs
• Convex neighborhood polynomial of graphs
• Combinatorial approach in counting the neighbors of cliques in a graph
• Polynomial representations of a balanced biclique common neighborhood system of graphs
• Independent sets in the neighborhood systems of balanced bicliques: optimization and polynomial representations
• Kramers-Wannier duality and Tutte polynomials
• On integral variations for roots of the Laplacian matching polynomial of graphs
• Counting with two-level polynomials
• On the location of roots of graph polynomials
• A little statistical mechanics for the graph theorist

This page was built for publication: Graph polynomials and their applications. II: Interrelations and interpretations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3064402)