| Спектральные инварианты графов и их приложения в комбинаторике | |
| Грюнвальд Л. А.1, Медных А. Д.2, Медных И. А.3 | |
| 1.1Институт математики им. С.Л. Соболева, Новосибирск, Россия | |
| Дата поступления 2023.12.28 | Аннотация. В данном исследовании мы представляем недавние результаты, полученные авторами. Они связаны со спектральными инвариантами графов, допускающих действие произвольной большой циклической группы. Для их иллюстрации мы используем семейство циркулянтных графов $G_{n} = C_{n}(s_1,s_2,\ldots,s_k).$ Полиномы Чебышева предоставляют важные аналитические инструменты для изучения свойств таких графов и их характеристических многочленов. В частности, это дает возможность найти аналитические выражения для количества остовных деревьев $\tau(n),$ числа корневых остовных лесов $f_G(n)$ и индекса Кирхгофа $Kf(G_{n})$ графа. Нас будет интересовать поведение этих инвариантов при достаточно больших $n.$ Мы приводим асимптотические формулы упомянутых выше инвариантов. Эти результаты были мотивированы проблемами, возникающими в теоретической физике, биологии и химии. |
| Ключевые слова спектральные инварианты графов, приложения в комбинаторике, количество остовных деревьев, число корневых остовных лесов, индекс Кирхгофа. | |
Библиография \bibitem{Austin60} Austin, T.~L.~(1960). The enumeration of point labelled chromatic graphs and trees. {\em Canad.~J.~Math.}, 12:535--545. \bibitem{BaiMe} Baigonagova, G.~A., Mednykh, A.~D.~(2019). Elementary formulas for Kirchhoff index of Moebius ladder and prism graphs. {\em Sib. Electron. Math. Rep.}, 16:1654--1661. \bibitem{BoePro} Boesch, F.~T., Prodinger,~H.~(1986). Spanning tree formulas and Chebyshev polynomials. {\em Graphs and Combinatorics}, 2(1):191--200. \bibitem{BB87} Boesch,~F.~T., Bogdanowicz,~Z.~R.~(1987). The number of spanning tress in a prism. {\em Internat. J. Comput. Math.}, 21:229--243. %\bibitem{Boy02} D.~W.~Boyd, %Mahlers Measure and Invariants of Hyperbolic Manifolds, %Number Theory for the Millennium, I (Urbana, Il, 2000). A K Peters, (2002), 127--143. \bibitem{Cay89} Cayley,~A.~(1889). A theorem on trees. {\em Quart. J. Pure Appl. Math.}, 23:376--378. \bibitem{Cheb} Chebotarev,~P.~(2008). Spanning forests and the golden ratio. {\em Discrete Appl. Math.}, 156:813–821. doi:10.1016/j.dam.2007.08.030 \bibitem{ChebSham} Chebotarev,~P., Shamis,~E.~(2006). Matrix forest theorems. arXiv:math/0602575 [math.CO]. %\bibitem{CondGra} M.~Conder, R.~Grande, %On embeddings of circulant graphs, %Electronic Journal of Combinatorics, 22(2) (2015), \#P2.28. \bibitem{Cinkir} Cinkir,~Z.~(2016). Effective resistances and Kirchhoff index of ladder graphs. {\em J. Math. Chem.}, 54(4):955--966. %\bibitem{PJDav} P.~J.~Davis, Circulant Matrices, AMS Chelsea Publishing, 1994. %\bibitem{EverWard} G.~Everest, T.~Ward, %\textit{Heights of polynomials and entropy in algebraic dynamics}. %(Springer Science \& Business Media, 2013). \bibitem{EvPo} Evdokimov,~S., Ponomarenko,~I.~(2004). Recognition and verification of an isomorphism of circulant graphs in polynomial time. {\em St. Petersburg Math. J.}, 15:813--835. \bibitem{GrMe} Grunwald,~L.~A., Mednykh,~I.~A.~(2022). The number of rooted forests in circulant graphs. {\em Ars Math. Contemp.}, 22(4):10, 12 pp. \bibitem{GutMoh} Gutman,~I., Mohar,~B.~(1996). The quasi-Wiener and the Kirchhoff indices coincide. {\em J. Chem. Inf. Comput. Sci.}, 36(5):982--985. \bibitem{Hil74} Hilton,~A.~J.~W.~(1974). Spanning trees and Fibonacci and Lucas numbers. {\em Fibonacci Q.}, 12:259--262. \bibitem{JinLiu} Jin,~Y., Liu,~C.~(2004). Enumeration for spanning forests of complete bipartite graphs. {\em Ars Comb.}, 70:135--138. \bibitem{KagMa} Kagan,~M., Mata,~B.~(2019). A physics perspective on the resistance distance for graphs. {\em Math. Comput. Sci.}, 13:105--115. \bibitem{Kir47} Kirchhoff,~G.~(1847). "Uber die Aufl"osung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Str"ome gef"uhrt wird. {\em Ann. Phys. Chem.}, 72:497--508. \bibitem{KwonMedMed2} Grunwald,~L.~A., Kwon,~Y.~S., Mednykh,~I.~A.~(2022). Counting rooted spanning forests for circulant foliation over a graph. {\em Tohoku Math. J. (2)}, 74(4):535--548. \bibitem{KwonMedMed1} Kwon,~Y.~S., Mednykh,~A.~D., Mednykh,~I.~A.~(2021). Complexity of the circulant foliation over a graph. {\em J. Algebraic Combin.}, 53(1):115--129. \bibitem{KwonMedMed} Kwon,~Y.~S., Mednykh,~A.~D., Mednykh,~I.~A.~(2017). On Jacobian group and complexity of the generalized Petersen graph $GP(n,k)$ through Chebyshev polynomials. {\em Linear Algebra Appl.}, 529:355--373. \bibitem{Kelmans} Kelmans,~A.~K., Chelnokov,~V.~M.~(1974). A certain polynomial of a graph and graphs with an extremal number of trees. {\em J. Comb. Theory Ser. B}, 16:197–214. doi:10.1016/0095-8956(74)90065-3 \bibitem{Klein} Klein,~D.~J., Randi'c,~M.~(1993). Resistance distance. {\em J. Math. Chem.}, 12:81--95. \bibitem{OKnill} Knill,~O.~(2014). Cauchy-Binet for pseudo-determinants. {\em Linear Algebra Appl.}, 459:522--547. doi:10.1016/j.laa.2014.07.013 \bibitem{Lukovits} Lukovits,~I., Nikoli'c,~S., Trinajsti'c,~N.~(1999). Resistance distance in regular graphs. {\em Int. J. Quantum Chem.}, 71(3):217–225. \bibitem{Luzhen} Luzhen~Ye~(2011). On the Kirchhoff index of some toroidal lattices. {\em Linear and Multilinear Algebra}, 59(6):645–650. \bibitem{MedMedK} Mednykh,~A.~D., Mednykh,~I.~A.~(2020). Kirchhoff index for circulant graphs and its asymptotics. {\em Dokl. Math.}, 102(2):392--395. \bibitem{MedMed2} Mednykh,~A.~D., Mednykh,~I.~A.~(2016). On the structure of the Jacobian group for circulant graphs. {\em Doklady Mathematics}, 94(1):445--449. \bibitem{Med1} Mednykh,~I.~A.~(2018). On Jacobian group and complexity of $I$-graph $I(n,k,l)$ through Chebyshev polynomials. {\em Arc Math. Contemp.}, 15(2):467--485. \bibitem{MedMed2018} Mednykh,~A.~D., Mednykh,~I.~A.~(2019). The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic. {\em Discrete Math.}, 342(6):1772--1781. \bibitem{MedMed2020A} Mednykh,~A.~D., Mednykh,~I.~A.~(2020). On rationality of generating function for the number of spanning trees in circulant graphs. {\em Algebra Colloq.}, 27(1):87--94. \bibitem{Muz} Muzychuk,~M.~(2004). A solution of the isomorphism problem for circulant graphs. {\em Proc. London Math. Soc. (3)}, 88:1--41. \bibitem{Palac} Palacios,~J.~L.~(2001). Closed-form formulas for Kirchhoff index. {\em Int. J. Quantum Chem.}, 81:135--140. \bibitem{Sed69} Sedláček,~J.~(1969). On the spanning trees of finite graphs. {\em Čas. Pěstování Mat.}, 94:217--221. \bibitem{Sed70} Sedláček,~J.~(1970). On the skeletons of a graph or digraph. In: Combinatorial Structures and their Applications, edited by R. Guy, M. Hanani, N. Saver, J. Schonheim, pp. 387--391. New York: Gordon and Breach. \bibitem{SW00} Shrock,~R., Wu,~F.~Y.~(2000). Spanning trees on graphs and lattices in $d$-dimensions. {\em J. Phys. A}, 33:3881--3902. \bibitem{SWZ16} Sun,~W., Wang,~S., Zhang,~J.~(2016). Counting spanning trees in prism and anti-prism graphs. {\em J. Appl. Anal. Comput.}, 6:65--75. \bibitem{Wein58} Weinberg,~L.~(1958). Number of trees in graph. {\em Proc. IRE}, 46:1954--1955. \bibitem{XG} Xiao,~W., Gutman,~I.~(2009). Resistance distance and Laplacian spectrum. {\em Theor. Chem. Acc.}, 110:284–289. \bibitem{ZY07} Zhang,~H., Yang,~Y.~(2007). Resistance distance and Kirchhoff index in circulant graphs. {\em Int. J. Quantum Chem.}, 107:330--339. \bibitem{ZKL} Zhu,~H.Y., Klein,~D.~J., Lukovits,~I.~(1996). Extensions of the Wiener number. {\em J. Chemical Information and Computer Sciences}, 36(3):420--428. | |
Сведения о финансировании и благодарности This survey was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF2022-0005). | |
| Spectral Invariants of Graphs and Their Applications to Combinatorics | |
| Grunwald L. A.1, Mednykh A. D.2, Mednykh I. A.3 | |
| 1.1Sobolev Institute of Mathematics, Novosibirsk, Russia | |
| Received 2023.12.28 | Abstract. In this research, we present recent results obtained by the authors. They related to spectral invariants of graphs admitting an arbitrary large cyclic group action. To illustrate them we use the family of circulant graphs $G_{n} = C_{n}(s_1,s_2,\ldots,s_k).$ The Chebyshev polynomials provide a significant analytical tools for studying the properties of such graphs and their characteristic polynomials. In particular, this gives a way to find analytical expressions for the number of spanning trees $\tau(n),$ the number of rooted spanning forests $f_G(n)$ and the Kirchhoff index $Kf(G_{n})$ of a graph. We are interested in the behaviour of these invariants for sufficiently large $n.$ We provide asymptotic formulas of the above mentioned invariants. These results were motivated by problems arising in theoretical physics, biology and chemistry. |
| Keywords Spectral Invariants of Graphs, Applications to Combinatorics, number of spanning trees, the number of rooted spanning forests, the Kirchhoff index. | |
References \bibitem{Austin60} Austin, T.~L.~(1960). The enumeration of point labelled chromatic graphs and trees. {\em Canad.~J.~Math.}, 12:535--545. \bibitem{BaiMe} Baigonagova, G.~A., Mednykh, A.~D.~(2019). Elementary formulas for Kirchhoff index of Moebius ladder and prism graphs. {\em Sib. Electron. Math. Rep.}, 16:1654--1661. \bibitem{BoePro} Boesch, F.~T., Prodinger,~H.~(1986). Spanning tree formulas and Chebyshev polynomials. {\em Graphs and Combinatorics}, 2(1):191--200. \bibitem{BB87} Boesch,~F.~T., Bogdanowicz,~Z.~R.~(1987). The number of spanning tress in a prism. {\em Internat. J. Comput. Math.}, 21:229--243. %\bibitem{Boy02} D.~W.~Boyd, %Mahlers Measure and Invariants of Hyperbolic Manifolds, %Number Theory for the Millennium, I (Urbana, Il, 2000). A K Peters, (2002), 127--143. \bibitem{Cay89} Cayley,~A.~(1889). A theorem on trees. {\em Quart. J. Pure Appl. Math.}, 23:376--378. \bibitem{Cheb} Chebotarev,~P.~(2008). Spanning forests and the golden ratio. {\em Discrete Appl. Math.}, 156:813–821. doi:10.1016/j.dam.2007.08.030 \bibitem{ChebSham} Chebotarev,~P., Shamis,~E.~(2006). Matrix forest theorems. arXiv:math/0602575 [math.CO]. %\bibitem{CondGra} M.~Conder, R.~Grande, %On embeddings of circulant graphs, %Electronic Journal of Combinatorics, 22(2) (2015), \#P2.28. \bibitem{Cinkir} Cinkir,~Z.~(2016). Effective resistances and Kirchhoff index of ladder graphs. {\em J. Math. Chem.}, 54(4):955--966. %\bibitem{PJDav} P.~J.~Davis, Circulant Matrices, AMS Chelsea Publishing, 1994. %\bibitem{EverWard} G.~Everest, T.~Ward, %\textit{Heights of polynomials and entropy in algebraic dynamics}. %(Springer Science \& Business Media, 2013). \bibitem{EvPo} Evdokimov,~S., Ponomarenko,~I.~(2004). Recognition and verification of an isomorphism of circulant graphs in polynomial time. {\em St. Petersburg Math. J.}, 15:813--835. \bibitem{GrMe} Grunwald,~L.~A., Mednykh,~I.~A.~(2022). The number of rooted forests in circulant graphs. {\em Ars Math. Contemp.}, 22(4):10, 12 pp. \bibitem{GutMoh} Gutman,~I., Mohar,~B.~(1996). The quasi-Wiener and the Kirchhoff indices coincide. {\em J. Chem. Inf. Comput. Sci.}, 36(5):982--985. \bibitem{Hil74} Hilton,~A.~J.~W.~(1974). Spanning trees and Fibonacci and Lucas numbers. {\em Fibonacci Q.}, 12:259--262. \bibitem{JinLiu} Jin,~Y., Liu,~C.~(2004). Enumeration for spanning forests of complete bipartite graphs. {\em Ars Comb.}, 70:135--138. \bibitem{KagMa} Kagan,~M., Mata,~B.~(2019). A physics perspective on the resistance distance for graphs. {\em Math. Comput. Sci.}, 13:105--115. \bibitem{Kir47} Kirchhoff,~G.~(1847). "Uber die Aufl"osung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Str"ome gef"uhrt wird. {\em Ann. Phys. Chem.}, 72:497--508. \bibitem{KwonMedMed2} Grunwald,~L.~A., Kwon,~Y.~S., Mednykh,~I.~A.~(2022). Counting rooted spanning forests for circulant foliation over a graph. {\em Tohoku Math. J. (2)}, 74(4):535--548. \bibitem{KwonMedMed1} Kwon,~Y.~S., Mednykh,~A.~D., Mednykh,~I.~A.~(2021). Complexity of the circulant foliation over a graph. {\em J. Algebraic Combin.}, 53(1):115--129. \bibitem{KwonMedMed} Kwon,~Y.~S., Mednykh,~A.~D., Mednykh,~I.~A.~(2017). On Jacobian group and complexity of the generalized Petersen graph $GP(n,k)$ through Chebyshev polynomials. {\em Linear Algebra Appl.}, 529:355--373. \bibitem{Kelmans} Kelmans,~A.~K., Chelnokov,~V.~M.~(1974). A certain polynomial of a graph and graphs with an extremal number of trees. {\em J. Comb. Theory Ser. B}, 16:197–214. doi:10.1016/0095-8956(74)90065-3 \bibitem{Klein} Klein,~D.~J., Randi'c,~M.~(1993). Resistance distance. {\em J. Math. Chem.}, 12:81--95. \bibitem{OKnill} Knill,~O.~(2014). Cauchy-Binet for pseudo-determinants. {\em Linear Algebra Appl.}, 459:522--547. doi:10.1016/j.laa.2014.07.013 \bibitem{Lukovits} Lukovits,~I., Nikoli'c,~S., Trinajsti'c,~N.~(1999). Resistance distance in regular graphs. {\em Int. J. Quantum Chem.}, 71(3):217–225. \bibitem{Luzhen} Luzhen~Ye~(2011). On the Kirchhoff index of some toroidal lattices. {\em Linear and Multilinear Algebra}, 59(6):645–650. \bibitem{MedMedK} Mednykh,~A.~D., Mednykh,~I.~A.~(2020). Kirchhoff index for circulant graphs and its asymptotics. {\em Dokl. Math.}, 102(2):392--395. \bibitem{MedMed2} Mednykh,~A.~D., Mednykh,~I.~A.~(2016). On the structure of the Jacobian group for circulant graphs. {\em Doklady Mathematics}, 94(1):445--449. \bibitem{Med1} Mednykh,~I.~A.~(2018). On Jacobian group and complexity of $I$-graph $I(n,k,l)$ through Chebyshev polynomials. {\em Arc Math. Contemp.}, 15(2):467--485. \bibitem{MedMed2018} Mednykh,~A.~D., Mednykh,~I.~A.~(2019). The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic. {\em Discrete Math.}, 342(6):1772--1781. \bibitem{MedMed2020A} Mednykh,~A.~D., Mednykh,~I.~A.~(2020). On rationality of generating function for the number of spanning trees in circulant graphs. {\em Algebra Colloq.}, 27(1):87--94. \bibitem{Muz} Muzychuk,~M.~(2004). A solution of the isomorphism problem for circulant graphs. {\em Proc. London Math. Soc. (3)}, 88:1--41. \bibitem{Palac} Palacios,~J.~L.~(2001). Closed-form formulas for Kirchhoff index. {\em Int. J. Quantum Chem.}, 81:135--140. \bibitem{Sed69} Sedláček,~J.~(1969). On the spanning trees of finite graphs. {\em Čas. Pěstování Mat.}, 94:217--221. \bibitem{Sed70} Sedláček,~J.~(1970). On the skeletons of a graph or digraph. In: Combinatorial Structures and their Applications, edited by R. Guy, M. Hanani, N. Saver, J. Schonheim, pp. 387--391. New York: Gordon and Breach. \bibitem{SW00} Shrock,~R., Wu,~F.~Y.~(2000). Spanning trees on graphs and lattices in $d$-dimensions. {\em J. Phys. A}, 33:3881--3902. \bibitem{SWZ16} Sun,~W., Wang,~S., Zhang,~J.~(2016). Counting spanning trees in prism and anti-prism graphs. {\em J. Appl. Anal. Comput.}, 6:65--75. \bibitem{Wein58} Weinberg,~L.~(1958). Number of trees in graph. {\em Proc. IRE}, 46:1954--1955. \bibitem{XG} Xiao,~W., Gutman,~I.~(2009). Resistance distance and Laplacian spectrum. {\em Theor. Chem. Acc.}, 110:284–289. \bibitem{ZY07} Zhang,~H., Yang,~Y.~(2007). Resistance distance and Kirchhoff index in circulant graphs. {\em Int. J. Quantum Chem.}, 107:330--339. \bibitem{ZKL} Zhu,~H.Y., Klein,~D.~J., Lukovits,~I.~(1996). Extensions of the Wiener number. {\em J. Chemical Information and Computer Sciences}, 36(3):420--428. | |
Acknowledgements This survey was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF2022-0005). | |
| Сведения об авторах Грюнвальд Л. А. 1.1 Медных А. Д. Медных И. А. |
| About the authors Grunwald L. A. 1.1 Mednykh A. D. Mednykh I. A. |
