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 |
| Summary: | 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). |
|---|