Linear Recurrence Relations for Graph Polynomials

DOI10.1007/978-3-540-78127-1_15zbMath1134.05099OpenAlexW1535123574MaRDI QIDQ5452182

Eldar Fischer, Johann A. Makowsky

Publication date: 25 March 2008

Published in: Pillars of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78127-1_15

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05) Graph theory (05C99)

Related Items (8)

On the Tutte and Matching Polynomials for Complete Graphs ⋮ Parameterized model checking of rendezvous systems ⋮ On sequences of polynomials arising from graph invariants ⋮ Unnamed Item ⋮ The enumeration of vertex induced subgraphs with respect to the number of components ⋮ Solutions of linear recurrence equations ⋮ Effective optimization with weighted automata on decomposable trees ⋮ Recurrence relations for graph polynomials on bi-iterative families of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A two-variable interlace polynomial
• Algorithmic uses of the Feferman-Vaught theorem
• The interlace polynomial of a graph
• The monadic theory of order
• Farrell polynomials on graphs of bounded tree width
• Recursively constructible families of graphs
• The vertex-cover polynomial of a graph
• The complexity of first-order and monadic second-order logic revisited
• On the cover polynomial of a digraph
• Upper bounds to the clique width of graphs
• Introduction to the theory of finite automata. Translated from the Russian. Translation edited by J.C. Shepherdson
• Recursive families of graphs
• On the relationship between NLC-width and linear NLC-width
• Fusion in relational structures and the verification of monadic second-order properties
• Modest theory of short chains. I
• A Tutte Polynomial for Coloured Graphs
• Handbook of Graph Grammars and Computing by Graph Transformation
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On spectra of sentences of monadic second order logic with counting
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Linear Recurrence Relations for Graph Polynomials