Trees in graph theory

## Primary tabs

# Trees in graph theory

Submitted by TheoricienQuantique on Tue, 05/03/2011 - 19:26

Forums:

I have a question regarding trees :

For a given and fix number V of vertices, what is the tree that maximizes both its diameter and degree ?

Any help would be greatly apprciated.

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Versions

(v1) by TheoricienQuantique 2011-05-03

## Re: Trees in graph theory

My question is very similar to the question solved by Moore graphs (As well as having the maximum possible number of vertices for a given combination of degree and diameter, Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth) but I want to restrain myself to trees only.

## Re: Trees in graph theory

Since the path has maximum diameter and the star has maximum degree there no tree that simultaneously maximizes both the degree and the diameter. The Moore graph example is irrelevant here.

## Re: Trees in graph theory

Actually I disagree, the answer are the Cayley graphs as I just realized recently. The point is to maximize both quantities at the same time, not just one.

## Re: Trees in graph theory

Forgot to specify, I mean the Cayley Graph of free groups, or in physics the Bethe lattices

## Re: Trees in graph theory

If this graph has N vertices, what is

a) the maximum degree , and

b) the diameter?

## Re: Trees in graph theory

The graph I am talking about has

N = 1 + ((1 + (Deg-1)^(Dia/2 + 1) - Deg) Deg)/((Deg-2)(Deg-1))

where Dia is the diameter (taken to be an even integer for simplicity) and Deg is the degree of all vertices excepts those on the outer rim (which have a degree of 1).

This graph is the tree with the maximum number of vertices for a given degree and diameter. So you are right I maximized N for a given Deg and Dia and not the opposite.

## Re: Trees in graph theory

A path will have maximum diameter but a star will have maximum degree.

I don't know what it means to maximize both functions.