Abstract
The degree/diameter problem asks: Given natural numbers d and k what is the order (that is, the maximum number of vertices) nd,k that can be contained in a graph of maximum degree d and diameter at most k? The degree/diameter problem is wide open for most values of d and k. A general upper bound exists; it is called the Moore bound. Graphs whose order attains the Moore bound are called Moore graphs. Since the degree/diameter problem is considered to be very difficult in general, it is worthwhile to consider it for special classes of graphs. In this paper we consider the degree/diameter problem on trees, special types of trees such as Cayley trees, caterpillars, lobsters, banana trees and firecracker trees, as well as for tree-like structures such as pseudotrees. We obtain new nd,k values and provide corresponding constructions.
| Original language | English |
|---|---|
| Pages (from-to) | 377-389 |
| Number of pages | 13 |
| Journal | AKCE International Journal of Graphs and Combinatorics |
| Volume | 10 |
| Issue number | 4 |
| Publication status | Published - 2013 |
Keywords
- Degree/diameter problem
- Pseudotrees
- Trees