Unit:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)Πληροφορική
Author:
Niklanovits Aikaterini
Supervisors info:
Δημήτριος Μ. Θηλυκός, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ
Original Title:
Expanding Graphs and Balanced Separators
Translated title:
Expanding Graphs and Balanced Separators
Summary:
A graph is an expander if it is sparse and has strong connectivity properties. Expanders are widely studied graphs, mainly due to their numerous applications in many different mathematical fields. The purpose of this thesis is to analyze the connections between expanders and other notions of graph theory, and study their substructures. Specifically, we will focus on the connection of balanced separators and expanders and provide an introduction on how the expansion of a graph is connected to the eigenvalues of its adjacency matrix. We will also study in detail the minors one can find in expanders.
Main subject category:
Science
Keywords:
expanding graphs, expanders, balanced separators, separators, graph theory
