40 citations · 96 across the 32 of their papers we have counts for
4 papers · 1 filter
On the location of roots of graph polynomials
Johann A. Makowsky, Elena V. Ravve, Nicolas K. Blanchard
Roots of graph polynomials such as the characteristic polynomial, the chromatic polynomial, the matching polynomial, and many others are widely studied. In this paper we examine to…
Recurrence Relations for Graph Polynomials on Bi-iterative Families of Graphs
Tomer Kotek, Johann A. Makowsky
We show that any graph polynomial from a wide class of graph polynomials yields a recurrence relation on an infinite class of families of graphs. The recurrence relations we obtain…
Connection Matrices and the Definability of Graph Parameters
Tomer Kotek, Johann A. Makowsky
In this paper we extend and prove in detail the Finite Rank Theorem for connection matrices of graph parameters definable in Monadic Second Order Logic with counting (CMSOL) from B…
Weighted Automata and Monadic Second Order Logic
Nadia Labai, Johann A. Makowsky
Let S be a commutative semiring. M. Droste and P. Gastin have introduced in 2005 weighted monadic second order logic WMSOL with weights in S. They use a syntactic fragment RMSOL of…