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
Best Answer
Circulant graphs can be used to realize the $\lfloor n\Delta/2 \rfloor$ bound in a large number of cases, and in the other cases, we can modify them slightly to achieve this bound.
For example, when $n=10$ and $\Delta=6$, we can take the distances $\{1,2,3\}$, which gives:
For example, when $n=10$ and $\Delta=5$, we can take the distances $\{1,2,5\}$, which gives:
For example, when $n=11$ and $\Delta=6$, we can take the distances $\{2,3,4\}$, which gives:
Finally, when $n$ is odd and $\Delta$ is odd (so $\Delta \leq n-2$), $n\Delta/2$ is not an integer, so we can't achieve the maximum with circulant graphs. The best we could possibly do is $\lfloor n\Delta/2 \rfloor$. To achieve this:
We take a $(\Delta-1)$-regular graph as above, but do not take distance $1$ edges (we need to take at most $(\Delta-1)/2 \leq (n-3)/2$ distances, so this is possible).
We observe that the edges of distance $1$ form a Hamilton cycle in the complement of the graph. We pick $(n-1)/2$ disjoint edges from this Hamilton cycle (i.e., no two edges share an endpoint), and add them to our construction.
For example, when $n=11$ and $\Delta=7$, we can take the above $6$-regular graph and add in edges around the outside as follows:
This gives $\lfloor n\Delta/2 \rfloor$ edges in every case (as expected).