Degree/diameter problem for trees and pseudotrees

Research output: Contribution to journalArticlepeer-review


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 languageEnglish
Pages (from-to)377-389
Number of pages13
JournalAKCE International Journal of Graphs and Combinatorics
Issue number4
Publication statusPublished - 2013


  • Degree/diameter problem
  • Pseudotrees
  • Trees


Dive into the research topics of 'Degree/diameter problem for trees and pseudotrees'. Together they form a unique fingerprint.

Cite this