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.

  • Is $d$ an upper bound on the diameter, or the exact diameter? – Ben Barber Sep 14 at 8:49
  • What about starting with a path of length $d-1$, then replacing one of its endpoints with a $(k-1)$-star? If you haven't used all your nodes, you can connect the remaining ones to the diametral path you've created. If that's not enough, you could make parallel subpaths to the diametral paths in such a way that you do not reduce the diameter. – Anthony Labarre Sep 14 at 8:54
  • @ Ben Barber: d is an upper bound on the diameter, thanks for the question. @ Anthony Labarre: That approach does seem promising, however I am not sure whether this will just approach a "good" solution, or actually guarantee the minimal number of edges. – Julian Nickerl Sep 19 at 12:08

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.

  • Thank you for your answer. Is this construction guaranteed to lead to the graph with the minimum number of edges? Are there references you can recommend? – Julian Nickerl Sep 19 at 12:16
  • I am not a graph theorist and do not know the literature, so I have no references for you right now. Except for the case of n-1 edges, there is no guarantee on the minimum number of edges. However, this shows that d has to be greater than 2 and less than log n in order for finding the minimum number of edges to be a challenge, when given k as a restriction. For searching, the only non-obvious suggestion I have is to try literature on computer networking. Gerhard "Surely Someone Did This Already" Paseman, 2018.09.19. – Gerhard Paseman Sep 19 at 14:39

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.

  • With this post, it looks like I am rediscovering Moore graphs. So check the Internet for Moore Graphs. Gerhard "There's A Reference For You" Paseman, 218.09.19. – Gerhard Paseman Sep 19 at 19:41
up vote 0 down vote accepted

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.