Geodesic
A spectral bound for vertex-transitive graphs and their spanning subgraphs
Biswas, Arindam1 ; Saha, Jyoti Prakash2
1 Department of Mathematical Sciences University of Copenhagen Universitetsparken 5 DK-2100 Copenhagen Denmark
2 Department of Mathematics Indian Institute of Science Education and Research Bhopal Bhopal Bypass Road Bhauri Bhopal 462066 Madhya Pradesh India
Algebraic Combinatorics, Tome 6 (2023) no. 3, pp. 689-706

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/alco.278
Classification : 05C25, 05C50
Keywords: Spectral gap, diameter, vertex-transitive graphs, discrete Cheeger–Buser inequality

Biswas, Arindam 1 ; Saha, Jyoti Prakash 2

1 Department of Mathematical Sciences University of Copenhagen Universitetsparken 5 DK-2100 Copenhagen Denmark
2 Department of Mathematics Indian Institute of Science Education and Research Bhopal Bhopal Bypass Road Bhauri Bhopal 462066 Madhya Pradesh India
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{ALCO_2023__6_3_689_0,
     author = {Biswas, Arindam and Saha, Jyoti Prakash},
     title = {A spectral bound for vertex-transitive graphs and their spanning subgraphs},
     journal = {Algebraic Combinatorics},
     pages = {689--706},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {3},
     year = {2023},
     doi = {10.5802/alco.278},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.5802/alco.278/}
}
TY  - JOUR
AU  - Biswas, Arindam
AU  - Saha, Jyoti Prakash
TI  - A spectral bound for vertex-transitive graphs and their spanning subgraphs
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 689
EP  - 706
VL  - 6
IS  - 3
PB  - The Combinatorics Consortium
UR  - http://geodesic.mathdoc.fr/articles/10.5802/alco.278/
DO  - 10.5802/alco.278
LA  - en
ID  - ALCO_2023__6_3_689_0
ER  - 
%0 Journal Article
%A Biswas, Arindam
%A Saha, Jyoti Prakash
%T A spectral bound for vertex-transitive graphs and their spanning subgraphs
%J Algebraic Combinatorics
%D 2023
%P 689-706
%V 6
%N 3
%I The Combinatorics Consortium
%U http://geodesic.mathdoc.fr/articles/10.5802/alco.278/
%R 10.5802/alco.278
%G en
%F ALCO_2023__6_3_689_0
Biswas, Arindam; Saha, Jyoti Prakash. A spectral bound for vertex-transitive graphs and their spanning subgraphs. Algebraic Combinatorics, Tome 6 (2023) no. 3, pp. 689-706. doi: 10.5802/alco.278

Cité par Sources :