Counting spanning trees in cobordism of two circulant graphs

N. V. Abrosimov ; G. A. Baigonakova ; I. A. Mednykh

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 15 (2018), pp. 1145-1157.

Résumé

We consider a family of graphs $H_n(s_1,\dots,s_k;t_1,\dots,t_\ell)$ that is a generalisation of the family of $I$-graphs, which, in turn, includes the generalized Petersen graphs. We present an explicit formula for the number $\tau(n)$ of spanning trees in these graphs in terms of the Chebyshev polynomials and find its asymptotics. Also, we show that the number of spanning trees can be represented in the form $\tau(n)=p\,n\,a(n)^2,$ where $a(n)$ is an integer sequence and $p$ is a prescribed integer depending on the number of even elements in the sequence $s_1,\dots,s_k,t_1,\dots,t_\ell$ and the parity of $n$.

Détail

Keywords: $I$-graph, Petersen graph, spanning tree, Chebyshev polynomial, Mahler measure.
Mots-clés : circulant graph

Bibliographie

[1] M. Aigner, G.M. Ziegler, Proofs from THE BOOK, Springer-Verlag, Berlin, 1998 | MR | Zbl

[2] M. Boben, T. Pisanski, A. Žitnik, “$I$-graphs and the corresponding configurations”, Journal of Combinatorial Designs, 13:6 (2005), 406–424 | DOI | MR | Zbl

[3] F.T. Boesch, H. Prodinger, “Spanning tree formulas and Chebyshev polynomials”, Graphs and Combinatorics, 2:1 (1986), 191–200 | DOI | MR | Zbl

[4] P.J. Davis, Circulant Matrices, AMS Chelsea Publishing, Madison, 1994 | MR | Zbl

[5] G. Everest, T. Ward, Heights of polynomials and entropy in algebraic dynamics, Springer Science Business Media, New York, 2013 | MR

[6] F. Harary, J.P. Hayes, H.-J. Wu, “A survey of the theory of hypercube graphs”, Computers Mathematics with Applications, 15:4 (1988), 277–289 | DOI | MR | Zbl

[7] N. Hartsfield, G. Ringel, Pearls in graph theory: a comprehensive introduction, Courier Dover Publications, New York, 2003 | MR

[8] B. Horvat, T. Pisanski, A. Žitnik, “Isomorphism checking of $I$-graphs”, Graphs and Combinatorics, 28:6 (2012), 823–830 | DOI | MR | Zbl

[9] Y.S. Kwon, A.D. Mednykh, I.A. Mednykh, “On Jacobian group and complexity of the generalized Petersen graph $GP(n, k)$ through Chebyshev polynomials”, Linear Algebra and its Applications, 529 (2017), 355–373 | DOI | MR | Zbl

[10] J.C. Mason, D.C. Handscomb, Chebyshev Polynomials, CRC Press, Boca Raton, 2003 | MR | Zbl

[11] A.D. Mednykh, I.A. Mednykh, “Asymptotics and Arithmetical Properties of Complexity for Circulant Graphs”, Doklady Mathematics, 97:2 (2018), 147–151 | DOI | Zbl

[12] I.A. Mednykh, “On Jacobian group and complexity of the $I$-graph $I(n,k,l)$ through Chebyshev polynomials”, Ars Mathematica Contemporanea, 15 (2018), 467–485 | DOI

[13] S.D. Nikolopoulos, C. Papadopoulos, “The number of spanning trees in $K_n$-complements of quasi-threshold graphs”, Graph Combinator, 20 (2004), 383–397 | DOI | MR | Zbl

[14] M. Petkovsěk, H. Zakrajsěk, “Enumeration of $I$-graphs: Burnside does it again”, Ars Mathematica Contemporanea, 2:2 (2009), 241–262 | DOI | MR | Zbl

[15] R. Shrock, F.Y. Wu, “Spanning trees on graphs and lattices in $d$-dimensions”, J. Phys. A: Math. Gen., 33 (2000), 3881–3902 | DOI | MR | Zbl

[16] W. Sun, S. Wang, J. Zhang, “Counting spanning trees in prism and anti-prism graphs”, J. Appl. Anal. Comput., 6 (2016), 65–75 | MR

[17] Chen Xiebin, Qiuying Lin, Fuji Zhang, “The number of spanning trees in odd valent circulant graphs”, Discrete Math., 282:1 (2004), 69–79 | DOI | MR | Zbl

[18] Zhang Yuanping, Xuerong Yong, M.J. Golin, “Chebyshev polynomials and spanning tree formulas for circulant and related graphs”, Discrete Math., 298:1 (2005), 334–364 | DOI | MR | Zbl

[19] Zhang Yuanping, Yong Xuerong, M.J. Golin, “The number of spanning trees in circulant graphs”, Discrete Math., 223:1 (2000), 337–350 | DOI | MR | Zbl