2
$\begingroup$

Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find closed form or a tight bound of the following quantity

$$ D = \sum_{e=\{u,v\} \in E} \frac{1}{d(u)+d(v)} $$

For example, suppose we have a complete graph with $n$ vertices. Then $D$ becomes $$ D = \frac{n(n-1)/2}{2(n-1)} = n/4$$.

For a path graph with $n$ vertices ($(n-1)$ edges) $D$ is $ \frac{(n-3)}{4}+2/3 $. My question is

  1. Is there any closed form of $D$ for general graph that involves $|V|$?
  2. If not is there any tight lower bound on the sum?
  3. Can we claim something like that the $D \geq |V|/k$ where k is a constant and $k<<|V|$?

*Yuval conjectured that $D \geq 1−1/n$ for a connect graph with $n$ vertices.

$\endgroup$
  • $\begingroup$ If your graph is a star on $n$ vertices, $D=1-1/n$. $\endgroup$ – Yuval Filmus Oct 12 '18 at 0:33
  • $\begingroup$ A tight lower bound involving only $|V|$ is zero: the graph could be empty. This also shows that $D$ doesn't depend just on $|V|$. $\endgroup$ – Yuval Filmus Oct 12 '18 at 0:59
  • $\begingroup$ It looks like that Yuval's observation is sharp. Can you update your question to say that "Yuval conjectured that $D\ge 1- 1/n$ for a connect graph with $n$ vertices", assuming @YuvalFilmus does not mind? $\endgroup$ – John L. Oct 12 '18 at 4:13
  • $\begingroup$ I certainly don't mind. It would also be interesting to find the maximum of $D$. $\endgroup$ – Yuval Filmus Oct 12 '18 at 4:20
2
$\begingroup$

Nice question!


There is no simple closed form of $D$ for general graphs that involves $|V|$ since $D$ can take at least two different values for any connected graph with more than 2 vertices. $D=1-\frac1{|V|}$ for a start graph and $D=\frac{|V|}4 > 1-\frac1{|V|}$ for a cycle graph. In fact, I would believe that the number of different values of $D$ for a graph of $n$ vertices grows exponentially with respect to $n$.


Yulval's tight lower bound

Claim: $D \geq 1−1/n$ for a connect graph with $n$ vertices, where the equality holds for and only for star graphs.

Proof. Let $G$ be a connect graph with $m$ edges. Since $G$ is connected, $m\ge n-1$, where the equality holds for and only for tree graphs. Let $e=\{u,v\}$ be an edge in $G$. $$\begin{aligned} d(u)+d(v) &= \Sigma_{s\in E,\, s \text { contains u}} 1 + \Sigma_{s\in E,\, s \text { contains v}} 1 \\ &= (1 + \Sigma_{s\in E,\, s \text { contains u},\, s\neq e} 1) + (1 + \Sigma_{s\in E,\, s \text { contains v},\, s\neq e} 1) \\ &= 2 + (\Sigma_{s\in E,\, s \text { contains u},\, s\neq e} 1 + \Sigma_{s\in E,\, s \text { contains v},\, s\neq e} 1) \\ &\le 2 + \Sigma_{s\in E,\, s\neq e} 1\\ &= 2 + (m -1)\\ &= m +1 \end{aligned}$$ The inequality above holds since the only edge that contains both $u$ and $v$ is $e$. The equality $d(u)+d(v)=m+1$ holds when every edge besides $e$ has a common vertex with $e$.

So, $$ D = \sum_{e=\{u,v\} \in E} \frac{1}{d(u)+d(v)} \ge m\, \frac1{m+1} = 1 - \frac1{m+1} \ge 1-\frac1n $$

The equality $D=1-\frac1n$ holds when there are $n-1$ edges in total and every two edge has a common vertex, which means the graph is a star graph.


There is no positive constant $k$ such that $D \geq |V|/k$, since $|V|/k$ goes to infinity while $1-1/|V|$ stays below 1 when $|V| goes to infinity.

| cite | improve this answer | |
$\endgroup$

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.