UPPER BOUND FOR EXPANSION RATE IN FINITE AND CONNECTED GRAPH
Expansion rate in finite and connected graph for a set of vertices is the least integer of the number of edges so that the neighborhood around that set of vertices have at least half the graphs weight. This study is intended to find the upper bound expansion rate which depends only on the graph a...
Saved in:
| Main Author: | |
|---|---|
| Format: | Final Project |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/47751 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| id |
id-itb.:47751 |
|---|---|
| spelling |
id-itb.:477512020-06-20T10:04:08ZUPPER BOUND FOR EXPANSION RATE IN FINITE AND CONNECTED GRAPH Aziez Rachmansyah, Kemal Indonesia Final Project finite and connected graph, expansion rate, eigenvalue, Laplace operator. INSTITUT TEKNOLOGI BANDUNG https://digilib.itb.ac.id/gdl/view/47751 Expansion rate in finite and connected graph for a set of vertices is the least integer of the number of edges so that the neighborhood around that set of vertices have at least half the graphs weight. This study is intended to find the upper bound expansion rate which depends only on the graph and the set of vertices. Eigenvalues of the Laplace operator is used as main tool. Two upper bounds are obtained and one of them is relatively close to the actual expansion rate. Examples for some graphs are given to see the closeness between the upper bounds and the expansion rate. This study is a rewriting, elaboration, and simulation of proofs by Fan R.K. Chung et al. (1997) dan Grigor’yan (2019). text |
| institution |
Institut Teknologi Bandung |
| building |
Institut Teknologi Bandung Library |
| continent |
Asia |
| country |
Indonesia Indonesia |
| content_provider |
Institut Teknologi Bandung |
| collection |
Digital ITB |
| language |
Indonesia |
| description |
Expansion rate in finite and connected graph for a set of vertices is the least integer
of the number of edges so that the neighborhood around that set of vertices have
at least half the graphs weight. This study is intended to find the upper bound
expansion rate which depends only on the graph and the set of vertices. Eigenvalues
of the Laplace operator is used as main tool. Two upper bounds are obtained and
one of them is relatively close to the actual expansion rate. Examples for some
graphs are given to see the closeness between the upper bounds and the expansion
rate. This study is a rewriting, elaboration, and simulation of proofs by Fan R.K.
Chung et al. (1997) dan Grigor’yan (2019). |
| format |
Final Project |
| author |
Aziez Rachmansyah, Kemal |
| spellingShingle |
Aziez Rachmansyah, Kemal UPPER BOUND FOR EXPANSION RATE IN FINITE AND CONNECTED GRAPH |
| author_facet |
Aziez Rachmansyah, Kemal |
| author_sort |
Aziez Rachmansyah, Kemal |
| title |
UPPER BOUND FOR EXPANSION RATE IN FINITE AND CONNECTED GRAPH |
| title_short |
UPPER BOUND FOR EXPANSION RATE IN FINITE AND CONNECTED GRAPH |
| title_full |
UPPER BOUND FOR EXPANSION RATE IN FINITE AND CONNECTED GRAPH |
| title_fullStr |
UPPER BOUND FOR EXPANSION RATE IN FINITE AND CONNECTED GRAPH |
| title_full_unstemmed |
UPPER BOUND FOR EXPANSION RATE IN FINITE AND CONNECTED GRAPH |
| title_sort |
upper bound for expansion rate in finite and connected graph |
| url |
https://digilib.itb.ac.id/gdl/view/47751 |
| _version_ |
1822927739551744000 |