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, 01.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",

year = "2025",

month = nov,

day = "1",

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.

PY - 2025/11/1

Y1 - 2025/11/1

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