5
$\begingroup$

Let $G=(V,E)$ be an $n$-vertex graph with $e$ edges.

For all $v\in V$, $d(v)$ is the degree of $v$, and $\bar{d}(v)$ is the ``non-degree" of $v$, that is, $\bar{d}(v)=(n-1)-d(v)$ (the degree of $v$ in the complement of $G$).

Define $k:=\left\lceil\sqrt{2e+1/4}+1/2\right\rceil$.

I want to show that \begin{align*} \sum_{v\in V}d(v)\bar{d}(v) & \geq 2(n-2)e - \frac{1}{4}\left(k^4-6k^3-(4e-11)k^2+(20e-6)k+4e(e-7)\right) \\ & = 2(n-2)e - \left(\binom{k}{2}-e\right)^2 + (4k-7)\left(\binom{k}{2}-e\right) - 6\binom{k}{3} \end{align*}

I will explain where this lower bound comes from. I believe that the graph, call it $G^*$, which achieves this lower bound is the following construction:

Take a single vertex from a $k$-clique (a complete graph with $k$ vertices) and remove exactly $r=\binom{k}{2}-e$ edges incident to it. Now add $n-k$ isolated vertices. In that case, there is one vertex of degree $k-r-1$, there are $r$ vertices of degree $k-2$, there are $k-r-1$ vertices of degree $k-1$, and $n-k$ vertices of degree $0$. Hence, for this construction, \begin{align*} \sum_{v\in V}d(v)\bar{d}(v) & = (k-r-1)\left(n-1-(k-r-1)\right) + r(k-2)\left(n-1-(k-2)\right) + (k-r-1)(k-1)\left(n-1-(k-1)\right) \\ & = (k-r-1)(n-k+r) + r(k-2)(n-k+1) + (k-r-1)(k-1)(n-k) \\ & = n(k^2-k-2r) - (k-r)(k-r-1) - r(k-1)(k-2) - k(k-1)(k-r-1) \\ & = 2en - 4e + 4e - r^2 +r(4k-3) - k^3 + k^2 \\ & = 2(n-2)e - \left(\binom{k}{2}-e\right)^2 + (4k-7)\left(\binom{k}{2}-e\right) + 4\binom{k}{2} - k^3 + k^2 \\ & = 2(n-2)e - \left(\binom{k}{2}-e\right)^2 + (4k-7)\left(\binom{k}{2}-e\right) - 6\binom{k}{3} \end{align*}

Could someone help me show that $G^*$ is indeed the "best" construction, with "best" meaning that $G^*$ is the unique graph which minimizes $\sum_{v \in V} d(v) \bar{d}(v)$ among all $n$-vertex graphs with $e$ edges. Thank you for your help!!

$\endgroup$

2 Answers 2

2
+50
$\begingroup$

I did not check your equations in detail, but the construction you described does not minimize $\sum_v d(v) \bar{d}(v)$ for the case of $n=5, e=4$. For this case:

  • $k:=\left\lceil\sqrt{2e+1/4}+1/2\right\rceil = \left\lceil\sqrt{8.25}+1/2\right\rceil = 4$

  • $r = {k \choose 2} - e = {4 \choose 2} - 4 = 6 - 4 = 2$

So by your construction, you start with the $4$-clique (more commonly denoted $K_4 =$ complete graph of $4$ nodes), pick one of the nodes $w$ (degree $3$) and remove $2$ of its edges. You end up with a $3$-cycle (the other $3$ unpicked nodes) and a single edge connecting $w$ to one of the nodes in the cycle. Then since $n=5$ you add $1$ isolated node. We call this resulting $n=5, e=4$ graph $A$. The five node degrees of $A$ are: $0, 1, 2, 2, 3$ and the sum is $sum(A) = 0+3+4+4+3 = 14$.

However, the star graph $B$ (where a center node connects to everyone else and those are all the connections) of $n=5, e=4$ has node degrees $1,1,1,1,4$ and the sum is $sum(B) =3+3+3+3+0 = 12 < sum(A)$.


I think your construction has a lot of merit, actually, but you missed a key fact:

As you noted, $\bar{d}(v)$ is the degree of $v$ in the complement graph $G' = (V, E')$ (i.e. where $e \in E'$ iff $e \notin E$). Therefore, the sum $\sum_v d(v) \bar{d}(v)$ is actually the same whether you consider $G$ or $G'$, since the complement of $G'$ is $G$ again. I.e. $\forall G: sum(G) = sum(G')$.

However, $e' = |E'| = {n \choose 2} - e$, and so if you start your construction procedure with $e$ or start with $e'$ you get two different graphs (obviously). It turns out they are not complements of each other, and can have different values for the sum.

My example is exactly that. If we use your construction but start with $n=5, e'=6$, we would have:

  • $k':=\left\lceil\sqrt{2e'+1/4}+1/2\right\rceil = \left\lceil\sqrt{12.25}+1/2\right\rceil = \lceil 3.5 + 0.5 \rceil = 4$

  • $r' = {k' \choose 2} - e' = {4 \choose 2} - 6 = 6 - 6 = 0$

So you would start with $K_4$, remove none of its edges, and simply add a $5$th isolated node. This graph, $C$, has node degrees are $3,3,3,3,0$ and $sum(C) = 3 + 3+ 3+ 3+ 0 = 12$. Since $C$ has $6$ edges, it does not qualify, but its complement $C'$ has $4$ edges and does qualify, and we already know $sum(C') = sum(C) = 12$. Now what is $C'$? It is exactly my star graph $B$.

To conclude: even if you think your procedure is great, after you use it on the given $(n, e)$ to get one graph $A$, you must also repeat your procedure starting with $(n, e' = {n \choose 2} - e)$ and get a different graph $C$. You are guaranteed that $C'$ has $e$ edges. So you need to pick $\min( sum(A), sum(C') )$.

I think it's an interesting question whether this two-pronged strategy will always minimize the sum for a given $(n,e)$.

$\endgroup$
1
  • $\begingroup$ It is interesting that you bring up $e'=\binom{n}{2}-e$ because originally I had defined $k:=\lceil \sqrt{2e'+1/4}+1/2 \rceil$ and $r:=\binom{k}{2}-e$, but I was noticing that for some values of $e'$ this resulted in a negative value for $r$, which did not make sense in this setting. I will look deeper into this two-pronged strategy. I appreciate your insight, thank you. $\endgroup$
    – Sarah
    Jun 9, 2019 at 1:37
0
$\begingroup$

Here is a quick proof that $G^*$ is optimal. We are trying to maximise $\sum \limits_{v \in V} (n-1)d(v) - d(v)^2$, noting that $\sum \limits_{v \in V} d(v) = 2e$. Since the function $(n-1)x-x^2$ is concave, if any two values of $d(v)$ differed by at least two, moving them closer together by $1$ would improve our sum. So the maximal sum possible would occur when all $d(v)$ were within $1$ of each other and therefore takes one of two possible values, which is exactly the amount obtained by $G^*$.

$\endgroup$
1
  • $\begingroup$ I am trying to minimize this sum $\endgroup$
    – Sarah
    Jun 4, 2019 at 14:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .