## Abstract

The degree/diameter problem asks: Given natural numbers d and k what is the order (that is, the maximum number of vertices) n_{d,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 n_{d,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