Graph polynomials: from recursive definitions to subset expansion formulas

DOI10.1093/LOGCOM/EXQ006MaRDI QIDQ2882559zbMATH OpenOpenAlexFDO

Authors B. Godlin, E. Katz, Johann A. Makowsky

Publication date 7 May 2012

Published in Journal of Logic and Computation (Search for Journal in Brave)

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

zbMATH Keywords

graph theoryfinite model theorygraph polynomialssecond order logic

Mathematics Subject Classification ID

Graph polynomials (05C31) Model theory of finite structures (03C13)

Abstract: Many graph polynomials, such as the Tutte polynomial, the interlace polynomial and the matching polynomial, have both a recursive definition and a defining subset expansion formula. In this paper we present a general, logic-based framework which gives a precise meaning to recursive definitions of graph polynomials. We then prove that in this framework every recursive definition of a graph polynomial can be converted into a subset expansion formula.

Recommendations

• Linear Recurrence Relations for Graph Polynomials
• A logician's view of graph polynomials
• The Tutte polynomial for graphs
• Recursively constructible families of graphs
• From a zoo to a zoology: Towards a general theory of graph polynomials

Cited in

(10)

• Graph polynomials: some questions on the edge
• scientific article; zbMATH DE number 6890347 (Why is no real title available?)
• Semantic equivalence of graph polynomials definable in second order logic
• My writing
• Graph polynomials and local graph operations
• Meta-theorems for graph polynomials
• The enumeration of vertex induced subgraphs with respect to the number of components
• On the location of roots of graph polynomials
• A logician's view of graph polynomials
• scientific article; zbMATH DE number 3893227 (Why is no real title available?)

This page was built for publication: Graph polynomials: from recursive definitions to subset expansion formulas

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