Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/44927
- Title
- Advances in the degree/diameter problem
- Author/Creator
-
Miller, Mirka
- Institution
- The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
- Description
- In extremal graph theory, there is a well-known fundamental problem, called the degree/diameter problem, which is to determine the largest (in terms of the number of vertices) graphs or digraphs of given maximum degree, respectively, maximum out-degree, and given diameter. General upper bounds, called Moore bounds, exist for the largest possible order of such graphs and digraphs of given maximum degree d (respectively, maximum out-degree d) and diameter k. In recent years, there have been many interesting new results in both the undirected and directed versions of the problem, resulting in improvements in both the lower bounds and the upper bounds on the largest possible number of vertices. However, quite a number of problems regarding the degree/diameter problem are still open. Some of these problems, such as constructing a Moore graph of degree d = 57 and diameter k = 2, or proving that such a graph cannot exist, have been open for 50 years. In this paper we present an overview of the current state of the degree/diameter problem, for both undirected and directed graphs, and we outline several related open problems.
- Relation
- VIJMDA: VI Jornadas de Matematica Discreta y Algoritmica. Proceedings of the VIJMDA (Lleida, Spain 21-23 July, 2008) p. 25-32
- Relation
- http://www.jmda2008.udl.cat/html/invitats.html
- Date
- 2008
- Publisher
- Universitat de Lleida
- Keyword(s)
-
graphs;
degree;
diameter;
Moore bound
- Resource Type
- conference paper
- Identifier
- http://hdl.handle.net/1959.13/44927
- Reviewed
25 Visitors
27 Hits
0 Downloads
