Standard

Spectrum of the Transposition graph. / Konstantinova, Elena V.; Kravchuk, Artem.

In: Linear Algebra and Its Applications, Vol. 654, 01.12.2022, p. 379-389.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Konstantinova EV, Kravchuk A. Spectrum of the Transposition graph. Linear Algebra and Its Applications. 2022 Dec 1;654:379-389. doi: 10.1016/j.laa.2022.08.033

Author

Konstantinova, Elena V. ; Kravchuk, Artem. / Spectrum of the Transposition graph. In: Linear Algebra and Its Applications. 2022 ; Vol. 654. pp. 379-389.

BibTeX

@article{55a5b308ef4543639958daf5cba5d15c,
title = "Spectrum of the Transposition graph",
abstract = "Transposition graph Tn is defined as a Cayley graph over the symmetric group generated by all transpositions. It is known that all eigenvalues of Tn are integers. However, an explicit description of the spectrum is unknown. In this paper we prove that for any integer k⩾0 there exists n(k) such that for any n⩾n(k) and any m∈{0,…,k}, m is an eigenvalue of Tn. In particular, it is proved that zero is an eigenvalue of Tn for any n≠2, and the integer 1 is an eigenvalue of Tn for any odd n⩾7 and for any even n⩾14. We also present exact values of the third and the fourth largest eigenvalues of Tn with their multiplicities.",
keywords = "Integral graph, Spectrum, Transposition graph",
author = "Konstantinova, {Elena V.} and Artem Kravchuk",
note = "Funding Information: The authors are very grateful to the referee for introducing us the reference [2] that helps to simplify the proofs of Theorems 4 and 5 . We also thank the referee for interesting suggestions and ideas on studying the eigenvalues zero and one. The work of Artem Kravchuk was supported by the Mathematical Center in Akademgorodok, under agreement No. 075-15-2022-281 with the Ministry of Science and High Education of the Russian Federation . Publisher Copyright: {\textcopyright} 2022 Elsevier Inc.",
year = "2022",
month = dec,
day = "1",
doi = "10.1016/j.laa.2022.08.033",
language = "English",
volume = "654",
pages = "379--389",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier Science Inc.",

}

RIS

TY - JOUR

T1 - Spectrum of the Transposition graph

AU - Konstantinova, Elena V.

AU - Kravchuk, Artem

N1 - Funding Information: The authors are very grateful to the referee for introducing us the reference [2] that helps to simplify the proofs of Theorems 4 and 5 . We also thank the referee for interesting suggestions and ideas on studying the eigenvalues zero and one. The work of Artem Kravchuk was supported by the Mathematical Center in Akademgorodok, under agreement No. 075-15-2022-281 with the Ministry of Science and High Education of the Russian Federation . Publisher Copyright: © 2022 Elsevier Inc.

PY - 2022/12/1

Y1 - 2022/12/1

N2 - Transposition graph Tn is defined as a Cayley graph over the symmetric group generated by all transpositions. It is known that all eigenvalues of Tn are integers. However, an explicit description of the spectrum is unknown. In this paper we prove that for any integer k⩾0 there exists n(k) such that for any n⩾n(k) and any m∈{0,…,k}, m is an eigenvalue of Tn. In particular, it is proved that zero is an eigenvalue of Tn for any n≠2, and the integer 1 is an eigenvalue of Tn for any odd n⩾7 and for any even n⩾14. We also present exact values of the third and the fourth largest eigenvalues of Tn with their multiplicities.

AB - Transposition graph Tn is defined as a Cayley graph over the symmetric group generated by all transpositions. It is known that all eigenvalues of Tn are integers. However, an explicit description of the spectrum is unknown. In this paper we prove that for any integer k⩾0 there exists n(k) such that for any n⩾n(k) and any m∈{0,…,k}, m is an eigenvalue of Tn. In particular, it is proved that zero is an eigenvalue of Tn for any n≠2, and the integer 1 is an eigenvalue of Tn for any odd n⩾7 and for any even n⩾14. We also present exact values of the third and the fourth largest eigenvalues of Tn with their multiplicities.

KW - Integral graph

KW - Spectrum

KW - Transposition graph

UR - http://www.scopus.com/inward/record.url?scp=85138174946&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2022.08.033

DO - 10.1016/j.laa.2022.08.033

M3 - Article

AN - SCOPUS:85138174946

VL - 654

SP - 379

EP - 389

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

ER -

ID: 38050705