Geodesic
Finding large expanders in graphs: from topological minors to induced subgraphs
Baptiste Louf1 ; Fiona Skerman1
1Uppsala Universitet
The electronic journal of combinatorics, Tome 30 (2023) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In this paper, we consider a structural and geometric property of graphs, namely the presence of large expanders. The problem of finding such structures was first considered by Krivelevich [SIAM J. Disc. Math. 32 1 (2018)]. Here, we show that the problem of finding a large induced subgraph that is an expander can be reduced to the simpler problem of finding a large topological minor that is an expander. Our proof is constructive, which is helpful in an algorithmic setting. We also show that every large subgraph of an expander graph contains a large subgraph which is itself an expander.
DOI : 10.37236/10859
Classification : 05C48, 05C83, 05C81, 60F10
Mots-clés : random walk, linear sized expander subgraphs

Baptiste Louf  1   ; Fiona Skerman  1

1 Uppsala Universitet 
@article{10_37236_10859,
     author = {Baptiste Louf and Fiona Skerman},
     title = {Finding large expanders in graphs: from topological minors to induced subgraphs},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {1},
     doi = {10.37236/10859},
     zbl = {1507.05054},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10859/}
}
TY  - JOUR
AU  - Baptiste Louf
AU  - Fiona Skerman
TI  - Finding large expanders in graphs: from topological minors to induced subgraphs
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10859/
DO  - 10.37236/10859
ID  - 10_37236_10859
ER  - 
%0 Journal Article
%A Baptiste Louf
%A Fiona Skerman
%T Finding large expanders in graphs: from topological minors to induced subgraphs
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10859/
%R 10.37236/10859
%F 10_37236_10859
Baptiste Louf; Fiona Skerman. Finding large expanders in graphs: from topological minors to induced subgraphs. The electronic journal of combinatorics, Tome 30 (2023) no. 1. doi: 10.37236/10859

Cité par Sources :