episciences.org_8839_1675109660
1675109660
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Fundamenta Informaticae
18758681
10
21
2022
Volume 186, Issues 14:...
On the Tutte and matching polynomials for complete graphs
Tomer
Kotek
Johann A.
Makowsky
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 nonnegative 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 SpeckerBlatter Theorem from 1981, which
studies modular recurrence relations of combinatorial sequences which count the
number of labeled graphs.
10
21
2022
8839
https://creativecommons.org/licenses/byncsa/4.0
arXiv:2112.06581
10.48550/arXiv.2112.06581
10.46298/fi20228839
https://fi.episciences.org/8839

https://fi.episciences.org/8839/pdf

https://fi.episciences.org/8839/pdf