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
APA
Vancouver
Author
Bibtex
}
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