Bounds on k-Regular Ramanujan Graphs and Separator Theorems

Expander graphs are a family of graphs that are highly connected. Finding explicit examples of expander graphs which are also sparse is a difficult problem. The best type of expander graph in a. certain sense is a Ramanujan graph. Families of graphs that have separator theorems fail to be Ramanujan if the vertex set gets sufficiently large. Using separator theorems to get an estimate on the expanding constant of graphs, we get bounds 011 the number of vertices for such fc-regular graphs in order for them to be Ramanujan.

Name thesis:degree_name

Master of Science

Discipline thesis:degree_discipline

Department of Mathematics and Computer Science

Year

2007

Author dc:creator

• Skees, James

• Mathematics

Repository record dc:identifier

https://digitalcommons.wku.edu/theses/379

OAI identifier oai:identifier

oai:digitalcommons.wku.edu:theses-1382