Fork me on GitHub
Math for the people, by the people.

User login

Trees in graph theory

Primary tabs

Trees in graph theory

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.


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.

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.

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.

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

If this graph has N vertices, what is
a) the maximum degree , and
b) the diameter?

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.

A path will have maximum diameter but a star will have maximum degree.
I don't know what it means to maximize both functions.

Subscribe to Comments for "Trees in graph theory"