Geodesic
Counting rooted spanning forests in cobordism of two circulant graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 814-823.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a family of graphs $H_n(s_1,\dots,s_k;t_1,\dots,t_\ell),$ which is a generalization of the family of $I$-graphs, which in turn, includes the generalized Petersen graphs and the prism graphs. We present an explicit formula for the number $f_{H}(n)$ of rooted spanning forests in these graphs in terms of Chebyshev polynomials and find its asymptotics. Also, we show that the number of rooted spanning forests can be represented in the form $f_{H}(n)=p a(n)^2,$ where $a(n)$ is an integer sequence and $p$ is a prescribed integer depending on the number of odd elements in the sequence $s_{1},\dots,s_{k},t_{1},\dots,t_{\ell}$ and the parity of $n$.
Keywords: $I$-graph, Petersen graph, prism graph, spanning forest, Chebyshev polynomial, Mahler measure.
Mots-clés : circulant graph 
@article{SEMR_2020_17_a133,
     author = {N. V. Abrosimov and G. A. Baigonakova and L. A. Grunwald and I. A. Mednykh},
     title = {Counting rooted spanning forests in cobordism of two circulant graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {814--823},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a133/}
}
TY  - JOUR
AU  - N. V. Abrosimov
AU  - G. A. Baigonakova
AU  - L. A. Grunwald
AU  - I. A. Mednykh
TI  - Counting rooted spanning forests in cobordism of two circulant graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 814
EP  - 823
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a133/
LA  - en
ID  - SEMR_2020_17_a133
ER  - 
%0 Journal Article
%A N. V. Abrosimov
%A G. A. Baigonakova
%A L. A. Grunwald
%A I. A. Mednykh
%T Counting rooted spanning forests in cobordism of two circulant graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 814-823
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a133/
%G en
%F SEMR_2020_17_a133
N. V. Abrosimov; G. A. Baigonakova; L. A. Grunwald; I. A. Mednykh. Counting rooted spanning forests in cobordism of two circulant graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 814-823. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a133/

[1] N.V. Abrosimov, G.A. Baigonakova, I.A. Mednykh, “Counting spanning trees in cobordism of two circulant graphs”, Sib. Electron. Mat. Izv., 15 (2018), 1145–1157 | MR | Zbl

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

[3] M. Boben, T. Pisanski, A. $\check{\textrm{Z}}$itnik, “$I$-graphs and the corresponding configurations”, J. Comb. Des., 13:6 (2005), 406–424 | DOI | MR | Zbl

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

[5] P.J. Davis, Circulant matrices, AMS Chelsea Publishing, New York, 1994 | MR | Zbl

[6] G. Everest, T. Ward, Heights of polynomials and entropy in algebraic dynamics, Springer, London, 1999 | MR | Zbl

[7] L.A. Grunwald, I.A. Mednykh, The number of rooted forests in circulant graphs, 2019, arXiv: 1907.02635 [math.CO] | Zbl

[8] F. Harary, J.P. Hayes, H.-J. Wu, “A survey of the theory of hypercube graphs”, Comput. Math. Appl., 15:4 (1988), 277–289 | DOI | MR | Zbl

[9] N. Hartsfield, G. Ringel, Pearls in graph theory. A comprehensive introduction, Dover Publications, Mineola, 2003 | MR | Zbl

[10] B. Horvat, T. Pisanski, A. $\check{\textrm{Z}}$itnik, “Isomorphism checking of $I$-graphs”, Graphs Comb., 28:6 (2012), 823–830 | DOI | MR | Zbl

[11] O. Knill, Counting rooted forests in a network, 2013, arXiv: 1307.3810 [math.SP]

[12] 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 Appl., 529 (2017), 355–373 | DOI | MR | Zbl

[13] L. Takács, “On the number of distinct forests”, SIAM J. Disc. Math., 3:4 (1990), 574–581 | DOI | MR | Zbl

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

[15] A.D. Mednykh, I.A. Mednykh, “Asymptotics and arithmetical properties of complexity for circulant graphs”, Dokl. Math., 97:2 (2018), 147–151 | DOI | MR | Zbl

[16] I.A. Mednykh, “On Jacobian group and complexity of the $I$-graph $I(n,k,l)$ through Chebyshev polynomials”, Arc Math. Contemp., 15:2 (2018), 467–485 | DOI | MR | Zbl

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

[18] M. Petkovs$\check{\textrm{e}}$k, H. Zakrajs$\check{\textrm{e}}$k, “Enumeration of $I$-graphs: Burnside does it again”, Ars Math. Contemp., 2:2 (2009), 241–262 | DOI | MR | Zbl

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

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

[21] C.J. Liu, Y. Chow, “Enumeration of forests in a graph”, Proc. Amer. Math. Soc., 83:3 (1981), 659–662 | DOI | MR | Zbl

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

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

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