A survey of the degree/diameter problem for undirected graphs
| Author(s) | Steller, Paul | |
| Date Accessioned | 2021-01-05T17:51:55Z | |
| Date Available | 2021-01-05T17:51:55Z | |
| Publication Date | 2020 | |
| SWORD Update | 2020-09-20T19:03:52Z | |
| Abstract | Given a fixed diameter and maximum degree, the degree/diameter problem involves finding the maximum possible order of a graph. The Moore bound represents the upper threshold that such an order may achieve, and only few graphs reach this threshold. In this thesis, we explore these graphs, including the elusive, hypothetical Moore graph of degree 57. This thesis will also examine graphs that fail to achieve equality in the Moore bound by only a few vertices. These graphs also turn out to be scarce. Finally, we look at a related problem, the Moore bipartite bound, and examine graphs that come very close to achieving this upper bound. | en_US |
| Advisor | Cioabă, Sebastian M. | |
| Degree | M.S. | |
| Department | University of Delaware, Department of Mathematical Sciences | |
| DOI | https://doi.org/10.58088/bffa-hh20 | |
| Unique Identifier | 1228909505 | |
| URL | https://udspace.udel.edu/handle/19716/28430 | |
| Language | en | |
| Publisher | University of Delaware | en_US |
| URI | https://login.udel.idm.oclc.org/login?url=https://www.proquest.com/dissertations-theses/survey-degree-diameter-problem-undirected-graphs/docview/2452102595/se-2?accountid=10457 | |
| Keywords | Algebraic graph theory | en_US |
| Keywords | Degree/diameter problem | en_US |
| Keywords | Graph theory | en_US |
| Keywords | Moore graphs | en_US |
| Title | A survey of the degree/diameter problem for undirected graphs | en_US |
| Type | Thesis | en_US |