Tomer Kotek ; Johann A. Makowsky - On the Tutte and matching polynomials for complete graphs

fi:8839 - Fundamenta Informaticae, October 21, 2022, Volume 186, Issues 1-4: Trakhtenbrot's centenary
On the Tutte and matching polynomials for complete graphsArticle

Authors: 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.


    Volume: Volume 186, Issues 1-4: Trakhtenbrot's centenary
    Published on: October 21, 2022
    Accepted on: July 7, 2022
    Submitted on: December 14, 2021
    Keywords: Mathematics - Combinatorics,05C30, 05C31 %68Q25, 68R10, 68U05

    Consultation statistics

    This page has been seen 147 times.
    This article's PDF has been downloaded 135 times.