Minimize edge number under diameter and max-degree constraint

Question

Given a number n of nodes, a diameter d (d>1) and a max-degree k. Let's assume d and k are chosen such that a graph with n nodes with the desired diameter and max-degree exists.

What is the minimum number of edges necessary to create a (connected) graph with n nodes, diameter d, and max-degree k? Is there a general construction rule to reach this graph?

Without the max-degree this question is trivially answered with n-1 by a star graph. How can we additionally deal with the max-degree? A better lower bound than n-1 would already be interesting.

Edit:d is meant to be an upper bound to the diameter.

Answer 1

If k=1 then n is at most 2 if you expect the graph to be connected. If k=2 then you have a cycle or path with diameter about n or n/2. ( I don't know if diameter is by counting edges or vertices, but the rest of this post will talk in approximate terms, so I won't care for exact results in what follows.) So consider k being 3 or greater.

Since you need n-1 edges, let's see what you can do with them. Try constructing a k-ary tree (root has k branches, some others have k-1 or fewer, most have degree 1), which leads to a diameter about c=log_k (n^2), which is small compared to n. So you need to add more edges only when d is smaller than c, or about log n or smaller.

Suppose you decide to add an edge to two leaves on the tree. Usually you won't reduce the graph diameter this way, but if you choose the leaves that have a common ancestor more than d/2 away, you have a start. For this edge affects not only those two leaves, but all leaves which are distance d/2 away from one of the two vertices. This is about k^d pairs of vertices brought to within the proper diameter by just one edge. Since there are about k^c pairs to deal with, you will need at least about k^(c-d) edges to follow this construction. For very small d, this may result in a number of edges which is a fractional power of n. (If d is too small, it may not be possible without violating the Max degree constraint. In which case, I'd really like to see the graph that does satisfy both constraints.)

Gerhard "More Than Just A Star-t" Paseman, 2018.09.14.

Answer 2

For k=3 and n=1+3(2^c -1), here is a toy example that you can generalize to some larger values of k, and see what it does to the diameter.

Do a 3-ary tree which looks like three binary trees joined at the roots, and divide each binary tree into a 0 subtree and 1-subtree of equal sizes (2^{c-1} -1 nodes each). Start at a zero subtree, pick a leaf,and draw an edge from that leaf to a leaf on a 1-subtree of a different binary tree. Then go from this leaf to a leaf on the 0-subtree of the third binary tree. Continue building this path, alternating between 0 and 1 subtrees of the different binary trees (so the path hits the groups in this repeating order 0x 1y 0z 1x 0y 1z), until you end up with a large cycle. I suspect the diameter of this graph is c, and that a k-ary version for k odd will lead to a diameter of c on a related graph of size n=1 + k*M(k,c), where M (k,c) is an expression for number of nodes of a depth c (k-1)-ary tree which I don't want to typeset right now. I think this example will be near optimal if not optimal in this study, and the result will involve kn edges. If so, this will tell you a lower bound for d in terms of k and n.

Gerhard "Likes The Pretty Cycles Made" Paseman, 2018.09.19.

Answer 3

I have found an answer to the question in a book by Béla Bollobás: Extremal Graph Theory. In chapter 4.1, he describes a lower bound:

Given maximal diameter $d$, maximal degree $k$, number of nodes $n$, number of edges $m$, the following inequality holds:

$m \geq \frac{n(n-1)(k-2)}{2((k-1)^d-1)}$

Sadly, I have not learned of any "construction rule" leading to a graph close to that bound.