Is there a simple way to construct such a graph? For example a fully connected graph obviously has degree of separation between every vertex of 1 but has maximal total degree. If we only wanted to minimise the total degree then I think the answer would be a star graph. But I want the average degree to be smallest rather than just relying on a single high degree vertex to be the common neighbour for all vertices. I can sort of see an algorithm starting with a cycle5 graph and adding nodes until the degree of separation between each pair of nodes is <= 2, but not sure if this would be optimal.

  • $\begingroup$ If the number of nodes is fixed, minimizing the average degree is the same as minimizing the number of edges. A connected graph on $n$ nodes must have at least $n-1$ edges, so the star graph is optimal. (I'm assuming that by "average" you mean the ordinary arithmetic average, i.e., add up the degrees of all the nodes and divide by the number of nodes.) $\endgroup$ – bof Nov 16 '18 at 5:40
  • 1
    $\begingroup$ Now, if you want to minimize the maximum degree (instead of the average degree), that's a famous problem called the degree-diameter problem. If you want to look that stuff up, you should learn the standard terminology. The "degree of separation" of two vertices is called their distance, the maximum degree of separation is called the diameter of the graph, a "fully connected" graph is called a complete graph. $\endgroup$ – bof Nov 16 '18 at 5:45
  • $\begingroup$ Great, thanks for the reference. Yes I guess I am after the degree-diameter problem - will look into it. :) $\endgroup$ – ben macintosh Nov 16 '18 at 6:51

As @bof points out, the star graph solves your problem (simple indeed):


It has $n-1$ edges for $n$ vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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