10.46298/fi-2022-8839
https://fi.episciences.org/8839
Kotek, Tomer
Tomer
Kotek
Makowsky, Johann A.
Johann A.
Makowsky
On the Tutte and matching polynomials for complete graphs
Let $T(G;X,Y)$ be the Tutte polynomial for graphs. We study the sequence
$t_{a,b}(n) = T(K_n;a,b)$ where $a,b$ are non-negative integers, and show that
for every $\mu \in \N$ the sequence $t_{a,b}(n)$ is ultimately periodic modulo
$\mu$ provided $a \neq 1 \mod{\mu}$ and $b \neq 1 \mod{\mu}$. This result is
related to a conjecture by A. Mani and R. Stones from 2016. The theorem is a
consequence of a more general theorem which holds for a wide class of graph
polynomials definable in Monadic Second Order Logic and some of its extensions,
such as the the independence polynomial, the clique polynomial, etc. We also
show similar results for the various substitution instances of the bivariate
matching polynomial and the trivariate edge elimination polynomial
$\xi(G;X,Y,Z)$ introduced by I. Averbouch, B. Godlin and the second author in
2008. All our results depend on the Specker-Blatter Theorem from 1981, which
studies modular recurrence relations of combinatorial sequences which count the
number of labeled graphs.
Comment: Accepted for publication in Fundamenta Informaticae 186(3): 1-19
(2022), the special volume celebrating B.A. Trakhtenbrot's centenary
episciences.org
Mathematics - Combinatorics
05C30, 05C31 %68Q25, 68R10, 68U05
Attribution-Non Commercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
2022-07-07
2022-10-21
2022-10-21
eng
journal article
arXiv:2112.06581
10.48550/arXiv.2112.06581
1875-8681
https://fi.episciences.org/8839/pdf
VoR
application/pdf
Fundamenta Informaticae
Volume 186, Issues 1-4: Trakhtenbrot's centenary
Researchers
Students