On the Tutte and matching polynomials for complete graphs

• Autorzy: Kotek Tomer , Makowsky Johann A.

Identyfikatory

URI

10.3233/FI-222124

• Języki publikacji: EN

Abstrakty

EN

Let T(G; X, Y) be the Tutte polynomial for graphs. We study the sequence ta,b(n) = T(Kn; a, b) where a, b are integers, and show that for every μ ∈ ℕ the sequence ta,b(n) is ultimately periodic modulo μ provided a ≠ 1 mod μ and b ≠ 1 mod μ. 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. This gives also similar results for the various substitution instances of the bivariate matching polynomial and the trivariate edge elimination polynomial ξ(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.

Słowa kluczowe

EN

mathematics - combinatorics; 05C30; 05C31 %68Q25; 68R10; 68U05

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 186, nr 1-4
• Strony: 155--173
• Opis fizyczny: Bibliogr. 40 poz.

Twórcy

autor

Kotek Tomer

• Berlin, Germany

autor

Makowsky Johann A.

• Department of Computer Science Israel Institute of Technology, Haifa, Israel

Bibliografia

• [1] Trakhtenbrot BA. Finite automata and monadic second order logic. Siberian Math. J, 1962. 3:101-131. English translation in: AMS Transl. 59 (1966), 23-55.
• [2] Fischer E, Makowsky J. Linear Recurrence Relations for Graph Polynomials. In: Avron A, Dershowitz N, Rabinowitz A (eds.), Boris (Boaz) A. Trakhtenbrot on the occasion of his 85th birthday, volume 4800 of LNCS. Springer, 2008 pp. 266-279. doi:10.1007/978-3-540-78127-1 15.
• [3] Blatter C, Specker E. Recurrence relations for the number of labeled structures on a finite set. In: Börger E, Hasenjaeger G, Rödding D (eds.), In Logic and Machines: Decision Problems and Complexity, volume 171 of Lecture Notes in Computer Science. Springer, 1984 pp. 43-61.
• [4] Courcelle B, Engelfriet J. Graph Structure and Monadic Second-order Logic, a Language Theoretic Approach. Cambridge University Press, 2012. doi:10.1017/CBO9780511977619.
• [5] Averbouch I, Godlin B, Makowsky JA. A most general edge elimination polynomial. In: International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 2008 pp. 31-42. doi:10.1007/978-3-540-92248-3 4.
• [6] Averbouch I, Godlin B, Makowsky JA. An extension of the bivariate chromatic polynomial. European Journal of Combinatorics, 2010. 31(1):1-17. doi:10.1016/j.ejc.2009.05.006.
• [7] Trinks M. The covered components polynomial: A new representation of the edge elimination polynomial. arXiv preprint arXiv:1103.2218, 2011.
• [8] Trinks M. Proving properties of the edge elimination polynomial using equivalent graph polynomials. arXiv preprint arXiv:1205.2205, 2012.
• [9] Tutte WT. A contribution to the theory of chromatic polynomials. Canadian journal of mathematics, 1954. 6:80-91.
• [10] Gessel IM, Wang DL. Depth-first search as a combinatorial correspondence. J. Comb. Theory, Ser. A, 1979. 26(3):308-313. doi:10.1016/0097-3165(79)90108-0.
• [11] Gessel IM. Enumerative applications of a decomposition for graphs and digraphs. Discrete mathematics, 1995. 139(1-3):257-271. doi:10.1016/0012-365X(94)00135-6.
• [12] Gessel IM, Sagan BE. The Tutte Polynomial of a Graph, Depth-first Search. The Electronic Journal of Combinatorics, 1996. pp. R9-R9. doi:10.37236/1267.
• [13] Pak IM. Computation of Tutte polynomials for complete graphs. URL https://www.math.ucla.edu/pak/papers/Pak Computation Tutte polynomial complete graphs.pdf.
• [14] Biggs N, Damerell R, Sand D. Recursive families of graphs. J. Combin. Theory Ser. B, 1972. 12(2):123-131. doi:10.1016/0095-8956(72)90016-0.
• [15] Godsil CD. Hermite polynomials and a duality relation for matchings polynomials. Combinatorica, 1981. 1(3):257-262. doi:10.1007/BF02579331.
• [16] Heilmann C, Lieb E. Theory of monomer-dymer systems. Comm. Math. Phys, 1972. 25:190-232. doi:10.1007/BF01877590.
• [17] Carlitz L. Congruence properties of the polynomials of Hermite, Laguerre and Legendre. Mathematische Zeitschrift, 1953. 59(1):474-483.
• [18] Mani A, Stones R. The number of labeled connected graphs modulo prime powers. SIAM. J. Discrete Math., 2016. 30.2:1046-1057. doi:10.1137/15M1024615.
• [19] Graham R, Knuth D, Patashnik O. Concrete Mathematics. Addison-Wesley, 2 edition, 1994.
• [20] Blatter C, Specker E. Le nombre de structures finies d’une théorie à charactère fin. Sciences Mathématiques, Fonds Nationale de la recherche Scientifique, Bruxelles, 1981. pp. 41-44.
• [21] Specker E. Application of Logic and Combinatorics to Enumeration Problems. In: Börger E (ed.), Trends in Theoretical Computer Science. Computer Science Press, 1988 pp. 141-169. Reprinted in: Ernst Specker, Selecta, Birkhäuser 1990, pp. 324-350. doi:10.1007/978-3-0348-9259-9 29.
• [22] Fischer E, Kotek T, Makowsky J. Application of Logic to Combinatorial Sequences and Their Recurrence Relations. In: Grohe M, Makowsky J (eds.), Model Theoretic Methods in Finite Combinatorics, volume 558 of Contemporary Mathematics, pp. 1-42. American Mathematical Society, 2011. doi:10.1090/conm/558/11047.
• [23] Balogh J, Bollobás B, Weinreich D. The Speed of Hereditary Properties of Graphs. J. Comb. Theory, Ser.B, 2000. 79(2):131-156. doi:10.1006/jctb.2000.1952.
• [24] Balogh J, Bollobás B, Weinreich D. The Penultimate Rate of Growth for Graph Properties. Eur. J. Comb., 2001. 22(3):277-289. doi:10.1006/eujc.2000.0476
• [25] Balogh J, Bollob´as B, Weinreich D. Measures on monotone properties of graphs. Discrete Applied
• Mathematics, 2002. 116(1-2):17-36. doi:10.1016/S0166-218X(01)00175-5.
• [26] Scheinerman ER, Zito J. On the size of hereditary classes of graphs. Journal of Combinatorial Theory, Series B, 1994. 61(1):16-39. doi:10.1006/jctb.1994.1027.
• [27] Redfield J. The theory of group-reduced distributions. Amer. J. Math., 1927. 49:433-455.
• [28] Read R. The enumeration of locally restricted graphs, I. J. London Math. Soc., 1959. 34:417-436.
• [29] Read R. The enumeration of locally restricted graphs, II. J. London Math. Soc., 1960. 35:344-351.
• [30] Polya G, Read R. Combinatorial enumeration of groups, graphs, and chemical compounds. Springer, 1987. doi:10.1007/978-1-4612-4664-0.
• [31] Harary F, Palmer E. Graphical Enumeration. Academic Press, 1973. ISBN:978-0-12-324245-7.
• [32] Fischer E. The Specker-Blatter theorem does not hold for quaternary relations. Journal of Combinatorial Theory, Series A, 2003. 103(1):121-136. doi:10.1016/S0097-3165(03)00075-X.
• [33] Specker E. Modular Counting and Substitution of Structures. Combinatorics, Probability and Computing, 2005. 14:203-210. doi:10.1017/S0963548304006698.
• [34] Fischer E, Makowsky JA. The Specker-Blatter Theorem revisited. In: COCOON, volume 2697 of Lecture Notes in Computer Science. Springer, 2003 pp. 90-101. doi:10.1007/3-540-45071-8 11.
• [35] Libkin L. Elements of Finite Model Theory. Springer, 2004. doi:10.1007/978-3-662-07003-1.
• [36] Alikhani S, Peng Yh. Introduction to domination polynomial of a graph. arXiv preprint arXiv:0905.2251, 2009.
• [37] Oboudi MR. On the roots of domination polynomial of graphs. Discrete Applied Mathematics, 2016. 205:126-131. doi:10.1016/j.dam.2015.12.010.
• [38] Arratia R, Bollob´as B, Sorkin GB. The interlace polynomial of a graph. Journal of Combinatorial Theory, Series B, 2004. 92(2):199-233. doi:10.1016/j.jctb.2004.03.003.
• [39] Courcelle B. A multivariate interlace polynomial and its computation for graphs of bounded clique-width. The Electronic Journal of Combinatorics, 2008. 15 pp. R69-R69. doi:10.37236/793.
• [40] Fischer E, Makowsky JA. The Specker-Blatter Theorem Revisited. In: Computing and Combinatorics: 9th Annual International Conference, COCOON 2003, volume 2697 of Springer Lecture Notes in Computer Science. 2003 pp. 90-101. doi:10.1007/3-540-45071-8 11.