[vc_empty_space][vc_empty_space]
The first two largest eigenvalues of Laplacian, spectral gap problem and Cheeger constant of graphs
Samuel O.a, Soeharyadi Y.a, Setyabudhi M.W.a
a Department of Mathematics, Institut Teknologi Bandung, Bandung, Jawa Barat, 40132, Indonesia
[vc_row][vc_column][vc_row_inner][vc_column_inner][vc_separator css=”.vc_custom_1624529070653{padding-top: 30px !important;padding-bottom: 30px !important;}”][/vc_column_inner][/vc_row_inner][vc_row_inner layout=”boxed”][vc_column_inner width=”3/4″ css=”.vc_custom_1624695412187{border-right-width: 1px !important;border-right-color: #dddddd !important;border-right-style: solid !important;border-radius: 1px !important;}”][vc_empty_space][megatron_heading title=”Abstract” size=”size-sm” text_align=”text-left”][vc_column_text]© 2017 Author(s).We show how the first two largest eigenvalues of Laplacian of a graph or smooth surface can be used to estimate the Cheeger constant of the graph. Particularly, we consider the problem of separating the graph into two large components of approximately equal volumes by making a small cut. This is the idea of Cheeger constant of a graph, which we want to relate to the spectral gap (the difference between the moduli of the first two largest eigenvalues of a Laplacian). We shall use Rayleigh variational characterization of the eigenvalues of the Laplacian to obtain the first two largest eigenvalues. The study reveals that spectral gap of a graph Γ correlates with the Cheeger constant hΓ of the graph. All our results are illustrated by some simple examples to give a clear insight of the concepts.[/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”Author keywords” size=”size-sm” text_align=”text-left”][vc_column_text][/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”Indexed keywords” size=”size-sm” text_align=”text-left”][vc_column_text]Cheeger constant,Graph,Laplacian,spectral gap[/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”Funding details” size=”size-sm” text_align=”text-left”][vc_column_text]This work is supported by PUPT DPRM Research Grant 2017. I also express my appreciation to my supervisors for the knowledge and inspiring me with brilliant creative ideas to this work.[/vc_column_text][vc_empty_space][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][vc_empty_space][megatron_heading title=”DOI” size=”size-sm” text_align=”text-left”][vc_column_text]https://doi.org/10.1063/1.5016648[/vc_column_text][/vc_column_inner][vc_column_inner width=”1/4″][vc_column_text]Widget Plumx[/vc_column_text][/vc_column_inner][/vc_row_inner][/vc_column][/vc_row][vc_row][vc_column][vc_separator css=”.vc_custom_1624528584150{padding-top: 25px !important;padding-bottom: 25px !important;}”][/vc_column][/vc_row]