eng
episciences.org
Fundamenta Informaticae
0169-2968
1875-8681
2022-10-21
Volume 186, Issues 1-4:...
10.46298/fi-2022-8839
8839
journal article
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 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.
https://fi.episciences.org/8839/pdf
Mathematics - Combinatorics
05C30, 05C31 %68Q25, 68R10, 68U05