A spectral bound for vertex-transitive graphs and their spanning subgraphs

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

A spectral bound for vertex-transitive graphs and their spanning subgraphs. / Biswas, Arindam; Saha, Jyoti Prakash.

In: Algebraic Combinatorics, Vol. 6, No. 3, 2023, p. 689-706.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Biswas, A & Saha, JP 2023, 'A spectral bound for vertex-transitive graphs and their spanning subgraphs', Algebraic Combinatorics, vol. 6, no. 3, pp. 689-706. https://doi.org/10.5802/alco.278

APA

Biswas, A., & Saha, J. P. (2023). A spectral bound for vertex-transitive graphs and their spanning subgraphs. Algebraic Combinatorics, 6(3), 689-706. https://doi.org/10.5802/alco.278

Vancouver

Biswas A, Saha JP. A spectral bound for vertex-transitive graphs and their spanning subgraphs. Algebraic Combinatorics. 2023;6(3):689-706. https://doi.org/10.5802/alco.278

Author

Biswas, Arindam ; Saha, Jyoti Prakash. / A spectral bound for vertex-transitive graphs and their spanning subgraphs. In: Algebraic Combinatorics. 2023 ; Vol. 6, No. 3. pp. 689-706.

Bibtex

@article{3d82839ff28f4c9d9cc2501756eb737b,
title = "A spectral bound for vertex-transitive graphs and their spanning subgraphs",
abstract = "For any finite, undirected, non-bipartite, vertex-transitive graph, we establish an explicit lower bound for the smallest eigenvalue of its normalised adjacency operator, which depends on the graph only through its degree and its vertex-Cheeger constant. We also prove an analogous result for a large class of irregular graphs, obtained as spanning subgraphs of vertex-transitive graphs. Using a result of Babai, we obtain a lower bound for the smallest eigenvalue of the normalised adjacency operator of a vertex-transitive graph in terms of its diameter and its degree.",
keywords = "diameter, discrete Cheeger-Buser inequality, Spectral gap, vertex-transitive graphs",
author = "Arindam Biswas and Saha, {Jyoti Prakash}",
note = "Publisher Copyright: {\textcopyright} 2023 Historia Actual Online.",
year = "2023",
doi = "10.5802/alco.278",
language = "English",
volume = "6",
pages = "689--706",
journal = "Algebraic Combinatorics",
issn = "2589-5486",
publisher = "Centre Mersenne",
number = "3",

}

RIS

TY - JOUR

T1 - A spectral bound for vertex-transitive graphs and their spanning subgraphs

AU - Biswas, Arindam

AU - Saha, Jyoti Prakash

N1 - Publisher Copyright: © 2023 Historia Actual Online.

PY - 2023

Y1 - 2023

N2 - For any finite, undirected, non-bipartite, vertex-transitive graph, we establish an explicit lower bound for the smallest eigenvalue of its normalised adjacency operator, which depends on the graph only through its degree and its vertex-Cheeger constant. We also prove an analogous result for a large class of irregular graphs, obtained as spanning subgraphs of vertex-transitive graphs. Using a result of Babai, we obtain a lower bound for the smallest eigenvalue of the normalised adjacency operator of a vertex-transitive graph in terms of its diameter and its degree.

AB - For any finite, undirected, non-bipartite, vertex-transitive graph, we establish an explicit lower bound for the smallest eigenvalue of its normalised adjacency operator, which depends on the graph only through its degree and its vertex-Cheeger constant. We also prove an analogous result for a large class of irregular graphs, obtained as spanning subgraphs of vertex-transitive graphs. Using a result of Babai, we obtain a lower bound for the smallest eigenvalue of the normalised adjacency operator of a vertex-transitive graph in terms of its diameter and its degree.

KW - diameter

KW - discrete Cheeger-Buser inequality

KW - Spectral gap

KW - vertex-transitive graphs

U2 - 10.5802/alco.278

DO - 10.5802/alco.278

M3 - Journal article

AN - SCOPUS:85164808348

VL - 6

SP - 689

EP - 706

JO - Algebraic Combinatorics

JF - Algebraic Combinatorics

SN - 2589-5486

IS - 3

ER -

ID: 382500709