Complexity of discrete Seifert foliations over a graph

Cover Page

Cite item

Full Text

Abstract

In the present paper, we study the complexity of an infinite family of graphs Hn = Hn(G1, G2, ..., Gm) that are discrete Seifert foliations over a graph H on m vertices with fibers G1, G2, ..., Gm. Each fiber Gi = Cn(si,1, si,2, ..., si,ki) of this foliation is the circulant graph on n vertices with jumps si,1, si,2, ..., si,ki. The family of discrete Seifert foliations is sufficiently large. It includes the generalized Petersen graphs, I-graphs, Y-graphs, H-graphs, sandwiches of circulant graphs, discrete torus graph and others. We obtain a closed formula for the number t(n) of spanning trees in Hn in terms of Chebyshev polynomials, investigate some arithmetical properties of this function and find its asymptotics as n → ∞.

About the authors

Young Soo Kwon

Yeungnam University

Email: smedn@mail.ru
Korea, Republic of, 280 Daehak-ro, Joyeong-dong, Gyeongsan, Gyeongsangbuk-do

A. D. Mednykh

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University

Author for correspondence.
Email: smedn@mail.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova street, Novosibirsk, 630090

I. A. Mednykh

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk State University

Email: smedn@mail.ru
Russian Federation, 4, Acad. Koptyug prospect, Novosibirsk, 630090; 1, Pirogova street, Novosibirsk, 630090

References

  1. Boesch F.T., Prodinger H. // Graphs and Combin. 1986. V. 2. 1. P. 191-200.
  2. Golin M.J., Xuerong Yong, Yuanping Zhang // Discrete Math. 2010. V. 310. P. 792-803.
  3. Sun W., Wang S., Zhang J. // J. Appl. Anal. Comput. 2016. V. 6. 1. P. 65-75.
  4. Wu F.Y. // J. Phys. A: Math. Gen. 1977. V. 10. P. L113-115.
  5. Shrock R., Wu F.Y. // J. Phys. A: Math. Gen. 2000. V. 33. P. 3881-3902.
  6. Guttmann A.J., Rogers M.D. // J. Phys. A: Math. Theor. 2012. V. 45. 49. 494001.
  7. Louis J. //Bull. Aust. Math. Soc. 2015. V. 92, 3. P. 365-373.
  8. Abrosimov N.V., Baigonakova G.A., Mednykh I.A. // Sib. Electronic Math. Rep. 2018. V. 15. P. 1145-1157.
  9. Kwon Y.S., Mednykh A.D., Mednykh I.A. // Linear Algebra Appl. 2017, V. 529, P. 355-373.
  10. Медных А.Д., Медных И.А. // ДАН. 2018. Т. 479. № 4. С. 363-367.
  11. Mednykh I.A. // Ars Math. Contemp. 2018. V. 15. P. 467-485.
  12. Horton J.D., Bouwer I.Z. // J. Combin. Theory. Ser. B. 1991. V. 53. P. 114-129.
  13. Kwon Y.S., Mednykh A.D., Mednykh I.A. // arXiv: 1811.03801v1 [math.CO] 09 Nov 2018.
  14. Lorenzini D. // J. Combin. Theory Ser. B. 2008. V. 98. 6. P. 1271-1300.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2019 Russian academy of sciences