Research output: Contribution to journal › Article › peer-review
Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics. / Mednykh, Alexander; Mednykh, Ilya.
In: Ars Mathematica Contemporanea, Vol. 23, No. 1, 2530, 2022.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Complexity of circulant graphs with non-fixed jumps, its arithmetic properties and asymptotics
AU - Mednykh, Alexander
AU - Mednykh, Ilya
N1 - Публикация для корректирровки.
PY - 2022
Y1 - 2022
N2 - In the present paper, we investigate a family of circulant graphs with non-fixed jumps Gn= Cβn(s1, . . . , sk, α1n, . . . , αln),1 ≥ s1> . . . > sk > [βn/2], 1 ≥ α1> . . . > α1≥ [β2].Here n is an arbitrary large natural number and integers s1, . . . , sk, α1, . . . , αl, β are supposed to be fixed. First, we present an explicit formula for the number of spanning trees in the graph Gn. This formula is a product of βsk -1 factors, each given by the n-th Chebyshev polynomial of the first kind evaluated at the roots of some prescribed polynomial of degree sk. Next, we provide some arithmetic properties of the complexity function. We show that the number of spanning trees in Gn can be represented in the form τ (n) = p n a(n)2, where a(n) is an integer sequence and p is a given natural number depending on parity of β and n. Finally, we find an asymptotic formula for τ (n) through the Mahler measure of the Laurent polynomials differing by a constant from 2k - Pk i=1(zst+ z-st). Keywords: Spanning tree, circulant graph, Laplacian matrix, Chebyshev polynomial, Mahler measure.
AB - In the present paper, we investigate a family of circulant graphs with non-fixed jumps Gn= Cβn(s1, . . . , sk, α1n, . . . , αln),1 ≥ s1> . . . > sk > [βn/2], 1 ≥ α1> . . . > α1≥ [β2].Here n is an arbitrary large natural number and integers s1, . . . , sk, α1, . . . , αl, β are supposed to be fixed. First, we present an explicit formula for the number of spanning trees in the graph Gn. This formula is a product of βsk -1 factors, each given by the n-th Chebyshev polynomial of the first kind evaluated at the roots of some prescribed polynomial of degree sk. Next, we provide some arithmetic properties of the complexity function. We show that the number of spanning trees in Gn can be represented in the form τ (n) = p n a(n)2, where a(n) is an integer sequence and p is a given natural number depending on parity of β and n. Finally, we find an asymptotic formula for τ (n) through the Mahler measure of the Laurent polynomials differing by a constant from 2k - Pk i=1(zst+ z-st). Keywords: Spanning tree, circulant graph, Laplacian matrix, Chebyshev polynomial, Mahler measure.
UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85149695642&origin=inward&txGid=56b695cebdb1e65a91582bc5686b0152
UR - https://www.mendeley.com/catalogue/4b78f3a6-59ec-3c4a-990b-8d4571da21de/
U2 - 10.26493/1855-3974.2530.e7c
DO - 10.26493/1855-3974.2530.e7c
M3 - Article
VL - 23
JO - Ars Mathematica Contemporanea
JF - Ars Mathematica Contemporanea
SN - 1855-3966
IS - 1
M1 - 2530
ER -
ID: 55718010