3
$\begingroup$

The title is pretty self explanatory. If I have $V$ nodes and $E$ edges in a connected undirected graph, is there a formula to determine an upper bound on the maximum possible diameter? The exact graph is unknown, but the number of edges and the number of vertices is. I do know that when $E=V(V-1)/2$ (complete graph), the maximum possible diameter is $1$, and when $E=V-1$ (line graph), the maximum possible diameter is $V-1$, but I have no idea about anything in between.

$\endgroup$
  • $\begingroup$ sorry, I'm not familiar with the conventions of such questions. 1) do you mean that are excluded graphs constituted for example of 2 disconnected complete sub graphs ( giving an infinite distance ) ? 2) are you focused on the proof or on the result ? $\endgroup$ – user354674 Oct 2 '16 at 23:06
  • $\begingroup$ 1. The graph must be connected. 2. I want a result, but I need a proof to verify it. $\endgroup$ – AlgorithmsX Oct 2 '16 at 23:16
3
+50
$\begingroup$

We assume that $v \geq n-1 $ and $v \leq \frac{n(n-1)}{2}$

Given $v$ edges and $n$ nodes, let's compute the minimal number of nodes $u$ needed to spend the excess of edges in a spending-hole $SH$:

We know that the saturation of $u$ nodes needs $\frac{n(n-1)}{2}$ edges and it remains $w = n-u$ edges to constitute a linear graph generator of long distances.

First, let's try to minimize $u$ and maximize $w$ in :

  • $n = w + u$
  • $v = w-1 + 1 + \frac{u(u-1)}{2}$

where $w-1$ is for the long distance subgraph , $\frac{u(u-1)}{2}$ for the spending-hole $SH$ and $1$ edge to join them.

  • $=> u' = \frac{(3+\sqrt{(8(v-n)+9)})}{2}$
  • $=> u = \lceil {u'} \rceil = \lceil {\frac{(3+\sqrt{(8(v-n)+9)})}{2} }\rceil$ ,

$ceil(u')$ because we deal with integers and $u'$ was just a computed bound.

Then we compute the remaining nodes $n-u$ , we take from the $SH$ as many edges needed to reach $n-u$ and we may compute the distance $d = n-u +1$ which must be added $1$ if the $SH$ is saturated, ie if $\frac{u(u-1)}{2}-u= v-n$ .

Numerical application :

/*
main(5,true) :
5 nodes :

for v=4 : 2 nodes will consume 1 edges from 1 ; it remains 3 nodes 3 edges,d =4

      5 : 3                    3               3 ;            2       2             3

      6 : 4                    5               6 ;            1       1             3
      7 : 4                    6               6 ;            1       1             2

      8 : 5                    8              10 ;            0       0             2
      9 : 5                    9              10 ;            0       0             2
     10 : 5                   10              10 ;            0       0             1

Note how the distance $d$ changes with the edges in excess and how it decreases by $1$ when the $SH$ is saturated. I recall that the number of edges is bounded by the question and we cannot have double edges, no edges or edges without nodes.

function main(n,all)
{
    var u , spent , spentmax , v , V = n*(n-1)/2 , res = n+" nodes :\n" , exm = -1,d , firstline = true ;

    for ( v = n-1 ; v <= V ; v ++ )
    {
        u = Math.ceil( (3+Math.sqrt(8*(v-n)+9))/2 ) ;
        spentmax = (u*(u-1)/2)  ;
        spent = (v-n+u) ;
        if(u!=exm || all )
        {
            if(u!=exm )
            {
                if( all ) res += "\n" ;
                exm = u ;               
            }

            d = 1 + n-u + ( spentmax == spent ? 0 : 1 );
            if( firstline )
                res += ( "for v="+v+" : "+u +" nodes will consume "+spent+" edges from "+spentmax+" ; it remains "+(n-u)+" nodes " + (v-spent) +
                                " edges,d ="+d+"\n" ) ;
            else
                res += ( "      "+v+" : "+u +"                    "+spent+"               "+spentmax+" ;            "+(n-u)+"       " + (v-spent) +
                                "             "+d+"\n" ) ;

            firstline = false ;
        }
    }
    return res ;
}

// scratchpad formalism to get the result by typing CTRL L at the end of the script
var z1 , z2 = main(5,false) ;     // number of nodes and true to get all the intermediate edges steps
z1=z2;

/*
main(12,false) :
12 nodes :
for v=11 : 2 nodes will consume 1 edges from 1 ; it remains 10 nodes 10 edges,d =11
      12 : 3                    3               3 ;            9       9            10
      13 : 4                    5               6 ;            8       8            10
      15 : 5                    8              10 ;            7       7             9
      18 : 6                   12              15 ;            6       6             8
      22 : 7                   17              21 ;            5       5             7
      27 : 8                   23              28 ;            4       4             6
      33 : 9                   30              36 ;            3       3             5
      40 : 10                  38              45 ;            2       2             4
      48 : 11                  47              55 ;            1       1             3
      57 : 12                  57              66 ;            0       0             2    */

Even if the proof is not fundamentally detailed, one can see that the construction is minimal, starting from a linear graph with $v = n-1$ and adding the edges in excess in a Spending hole ( or a ball of wool if one prefers ). When the latter is saturated, we "sacrify" a new node until a new saturation. When all the edges in excess have used a minimum of nodes, it remains a piece of linear graph which is joined to the $SH$ by one edge to one node.

The same question with the possibility of not connection is interesting too ... This kind of problems has a lot of applications when the algorithm may add nodes at its convienience ( Steiner tree problems family ).

ps : feel free to edit and correct obscure translations, TY

$\endgroup$
  • $\begingroup$ Starting from the same intuition than @heptagon in August, I find a similar result but at the opposite I have no doubt that this solution is valid for any values of $n$ and $v$. Then anteriority credit to Heptagon which is confirmed by this answer $\endgroup$ – user354674 Oct 3 '16 at 3:14
  • $\begingroup$ This looks pretty good, but you might need to clean it up a bit. You have phrases like "$v$ vertices and $n$ nodes" and you don't mention edges. I am pretty sure that vertices and nodes are the same thing. I will also wait until the end of the week to award the bounty to see if anyone else can provide a better answer. $\endgroup$ – AlgorithmsX Oct 3 '16 at 3:28
  • $\begingroup$ @AlgorithmsX : yes, I used the word "vertice" for "edge" ! I use sometimes a translator but not this time. I'll change the word now $\endgroup$ – user354674 Oct 3 '16 at 3:30
  • $\begingroup$ Also, are you adding nodes and edges? The number of nodes and number of edges should be parameters in some function or algorithm that predicts the maximum possible diameter. $\endgroup$ – AlgorithmsX Oct 3 '16 at 3:33
  • $\begingroup$ @AlgorithmsX You have them. I let you read the answer and test the javascript in scratchpad. If you see another big error of translation ( you may because you know well the question ), please let me know ... Note that as a puzzle fan, I always wait for better answers than the mines, it's better to learn that to be the best in a desert :) $\endgroup$ – user354674 Oct 3 '16 at 3:38
2
$\begingroup$

This is not a complete answer but rather an observation which leads to good results in some special cases. An interesting family of graphs to consider is the following. Take a complete graph $K_k$ and draw a simple path od length $v-k$ from one of its vertices. The thing you obtain has $v$ vertices, $v-(k^2-3k)/2$ edges, and diameter $v-k+1$. (The diameter is attained at a furthest point on the path and any vertex in $K_k$ that is not on the path.) A straightforward computation shows that you can get a graph with diameter $$V-\left\lceil\sqrt{2E-2V+\frac94}+\frac12\right\rceil,$$ $V$ vertices, and $E$ edges. Note that this bound is asymptotically best possible when there are not too many edges, that is, when $E=o(V^2)$, because then you get a graph with diameter $V+o(V)$. My bound is not supposed to be good for large $E$ though.

$\endgroup$
  • $\begingroup$ I added a bounty to this question. $\endgroup$ – AlgorithmsX Oct 2 '16 at 22:01
  • $\begingroup$ interesting intuitive answer ... I found it too but it is possible to elaborate around. I don't understand your final note ... $\endgroup$ – user354674 Oct 2 '16 at 23:49

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.