On the structure of Laplacian characteristic polynomial for circulant foliation

Standard

On the structure of Laplacian characteristic polynomial for circulant foliation. / Kwon, Y.S.; Mednykh, A.D.; Mednykh, I.A.

In: Discrete Applied Mathematics, Vol. 375, 15.11.2025, p. 338-349.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{70e3ecd9ce51482290a8adf430aef41f,

title = "On the structure of Laplacian characteristic polynomial for circulant foliation",

abstract = "In this paper, we describe the structure of the Laplacian characteristic polynomial for the infinite family of graphs obtained as a circulant foliation over a graph on vertices with fibers Each fiber of this foliation is the circulant graph on vertices with jumps This family includes the family of generalized Petersen graphs, -graphs, sandwiches of circulant graphs, discrete torus graphs and others. We show that the characteristic polynomial for such graphs can be decomposed into a finite product of algebraic functions evaluated at the roots of a linear combination of Chebyshev polynomials. Also, we prove that the characteristic polynomial can be represented in the form where is a sequence of integer polynomials and is a prescribed integer polynomial depending on the number of odd elements in the set of Moreover, we use the obtained results to produce analytic formulas for spectral graph invariants, such as the number of spanning trees and the number of spanning rooted forests.",

keywords = "Spanning forest, Rooted forest, Circulant graph, I-graph, Y-graph, H-graph, Laplacian matrix, Chebyshev polynomial",

author = "Y.S. Kwon and A.D. Mednykh and I.A. Mednykh",

note = "The first author was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2018R1D1A1B05048450). The second and the third authors were supported by the Mathematical Center in Akademgorodok, agreement no. 075-15-2019-1613 with the Ministry of Science and Higher Education of the Russian Federation.",

year = "2025",

month = nov,

day = "15",

doi = "10.1016/j.dam.2025.06.046",

language = "English",

volume = "375",

pages = "338--349",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier Science Publishing Company, Inc.",

}

RIS

TY - JOUR

T1 - On the structure of Laplacian characteristic polynomial for circulant foliation

AU - Kwon, Y.S.

AU - Mednykh, A.D.

AU - Mednykh, I.A.

N1 - The first author was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2018R1D1A1B05048450). The second and the third authors were supported by the Mathematical Center in Akademgorodok, agreement no. 075-15-2019-1613 with the Ministry of Science and Higher Education of the Russian Federation.

PY - 2025/11/15

Y1 - 2025/11/15

N2 - In this paper, we describe the structure of the Laplacian characteristic polynomial for the infinite family of graphs obtained as a circulant foliation over a graph on vertices with fibers Each fiber of this foliation is the circulant graph on vertices with jumps This family includes the family of generalized Petersen graphs, -graphs, sandwiches of circulant graphs, discrete torus graphs and others. We show that the characteristic polynomial for such graphs can be decomposed into a finite product of algebraic functions evaluated at the roots of a linear combination of Chebyshev polynomials. Also, we prove that the characteristic polynomial can be represented in the form where is a sequence of integer polynomials and is a prescribed integer polynomial depending on the number of odd elements in the set of Moreover, we use the obtained results to produce analytic formulas for spectral graph invariants, such as the number of spanning trees and the number of spanning rooted forests.

AB - In this paper, we describe the structure of the Laplacian characteristic polynomial for the infinite family of graphs obtained as a circulant foliation over a graph on vertices with fibers Each fiber of this foliation is the circulant graph on vertices with jumps This family includes the family of generalized Petersen graphs, -graphs, sandwiches of circulant graphs, discrete torus graphs and others. We show that the characteristic polynomial for such graphs can be decomposed into a finite product of algebraic functions evaluated at the roots of a linear combination of Chebyshev polynomials. Also, we prove that the characteristic polynomial can be represented in the form where is a sequence of integer polynomials and is a prescribed integer polynomial depending on the number of odd elements in the set of Moreover, we use the obtained results to produce analytic formulas for spectral graph invariants, such as the number of spanning trees and the number of spanning rooted forests.

KW - Spanning forest

KW - Rooted forest

KW - Circulant graph

KW - I-graph

KW - Y-graph

KW - H-graph

KW - Laplacian matrix

KW - Chebyshev polynomial

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=105009414495&origin=inward

U2 - 10.1016/j.dam.2025.06.046

DO - 10.1016/j.dam.2025.06.046

M3 - Article

VL - 375

SP - 338

EP - 349

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -

ID: 68295072