Spanning trees with small diameters

Abstract

A spanning tree with small diameter of a graph has many applications. In this paper we first make the following conjecture and show that the condition is best possible if it is true. If a connected graph satisfies , then has a spanning tree with diameter at most , where is an integer. We next prove that the conjecture holds if is even or . Moreover, we prove that if is odd and , then has a spanning tree with diameter at most .

Keywords

• spanning tree
• diameter
• minimum degree