<blockquote>
  <p>Given a weighted undirected graph $G = (V, E)$ with maximum degree $\mu$ and with positive edge weights, is it possible to construct another graph $H = (V \cup V', E')$ with maximum degree $\mu' = o(\mu)$ (ignoring poly-log factors) such that the following two conditions are satisfied: (1) the exact distance between each pair of vertices $u, v$ remains unchanged; and (2) each edge in $H$ has a positive weight?</p>
</blockquote>

<p>Has this problem been studied? Does this problem have a name? Are there any known lower and/or upper bounds on $\mu'$? Are there efficient algorithms to construct, if at all possible, such a graph $H$? What if I am also interested in the poly-log factors? </p>

<p>Do the answer to any of the above questions change if we consider the special case of unweighted graphs? </p>

<p>Clearly, the problem is of interest only if $\mu = \Omega(|V|^{\varepsilon})$ for some $\varepsilon &gt; 0$. Also, note that the problem is extremely trivial if we do not require the second condition. Also, assume that $G$ is a connected graph.</p>

CC BY-SA 3.0
2012-12-12T02:46:24.130Z
So, if $\mu=\Theta(|V|^{\epsilon})$, you want $\mu' =  O(|V|^{\delta})$ for some $\delta < \epsilon$?
Neal Young
CC BY-SA 3.0
2012-12-12T02:49:07.043Z
Let $G$ be a star with $n$ edges in which each edge has weight/length $1$. There is no graph $G'$ s.t. $d_G(u,v) = d_{G'}(u,v)$ for every $u,v\in V(G)$ and $\mu' < \mu = n$.
Yury
CC BY-SA 3.0
2012-12-12T03:06:51.530Z
@Rachit, to be clear, by "positive" you mean strictly positive, right?  (Otherwise you can root a binary tree around each vertex or some such..?)  If so I agree with Yuri's example.
Neal Young
CC BY-SA 3.0
2012-12-12T15:41:24.597Z
@Yury --- haha! I should have thought about it! I guess your answer generalizes to graphs with any edge density. In particular, we can have a star graph attached to one single node and then the answer to my question should be in negative (though I haven't proved it formally; will be very happy to be proved wrong). Interesting!
Rachit
CC BY-SA 3.0
2012-12-12T15:48:55.763Z
@Rachit: Suppose that we have a graph with edge lengths equal to 1. Let $v$ be a vertex such that no two neighbors of $v$ are adjacent then we cannot decrease the degree of $v$. In particular, if $G$ is triangle-free, we cannot decrease the degree of any vertex.
Yury
CC BY-SA 3.0
2012-12-12T19:47:12.400Z
@Yuri If you have a star with root $x$ and leaves $y_1, \ldots y_n$, doesn't a complete binary tree with root x, leaves $y_1, \ldots y_n$ and edge lengths $1/\log n$ work? You can generalize this to any unweighted grap I think.
Sasho Nikolov
CC BY-SA 3.0
2012-12-12T20:24:36.227Z
@SashoNikolov: No. The distance between every two leaves is 2 in a star; but the distance between some leaves in a complete binary tree is less than 2. In general, suppose that there is a graph $G'$ s.t. $d(x, y_i) = 1$ and $d(x_i, x_j) =2$ for every $i,j$. Consider shortest paths from $x$ to $y_i$ in $G'$ (one path for each $i$). These shortest paths cannot share vertices except for $x$ since if $u\neq x$ belongs to shortest paths from $x$ to $y_i$ and $x$ to $y_j$ then $d(y_i, y_j) \leq d(u, y_i) + d(u, y_j) = d(x, y_i) + d(x, y_j) - 2d(x,u) = 2 - 2d(x,u) < 2$. Thus $\deg x \geq n$.
Yury
CC BY-SA 3.0
2012-12-12T21:52:38.853Z
hehe, of course you are right, that was silly of me.
Sasho Nikolov
<graph-theory><graph-algorithms>
Reducing the maximum degree in a graph
Rachit
# Reducing the maximum degree in a graph

(Asked by: username_0 on 2012-12-11)

> Given a weighted undirected graph $G = (V, E)$ with maximum degree $\mu$ and with positive edge weights, is it possible to construct another graph $H = (V \cup V', E')$ with maximum degree $\mu' = o(\mu)$ (ignoring poly-log factors) such that the following two conditions are satisfied: (1) the exact distance between each pair of vertices $u, v$ remains unchanged; and (2) each edge in $H$ has a positive weight?

Has this problem been studied? Does this problem have a name? Are there any known lower and/or upper bounds on $\mu'$? Are there efficient algorithms to construct, if at all possible, such a graph $H$? What if I am also interested in the poly-log factors?

Do the answer to any of the above questions change if we consider the special case of unweighted graphs?

Clearly, the problem is of interest only if $\mu = \Omega(|V|^{\varepsilon})$ for some $\varepsilon > 0$. Also, note that the problem is extremely trivial if we do not require the second condition. Also, assume that $G$ is a connected graph.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: So, if $\mu=\Theta(|V|^{\epsilon})$, you want $\mu' =  O(|V|^{\delta})$ for some $\delta < \epsilon$?  
> **username_2**: Let $G$ be a star with $n$ edges in which each edge has weight/length $1$. There is no graph $G'$ s.t. $d_G(u,v) = d_{G'}(u,v)$ for every $u,v\in V(G)$ and $\mu' < \mu = n$.  
> **username_1**: @Rachit, to be clear, by "positive" you mean strictly positive, right?  (Otherwise you can root a binary tree around each vertex or some such..?)  If so I agree with Yuri's example.  
> **username_0**: @Yury --- haha! I should have thought about it! I guess your answer generalizes to graphs with any edge density. In particular, we can have a star graph attached to one single node and then the answer to my question should be in negative (though I haven't proved it formally; will be very happy to be proved wrong). Interesting!  
> **username_2**: @Rachit: Suppose that we have a graph with edge lengths equal to 1. Let $v$ be a vertex such that no two neighbors of $v$ are adjacent then we cannot decrease the degree of $v$. In particular, if $G$ is triangle-free, we cannot decrease the degree of any vertex.  
> **username_3**: @Yuri If you have a star with root $x$ and leaves $y_1, \ldots y_n$, doesn't a complete binary tree with root x, leaves $y_1, \ldots y_n$ and edge lengths $1/\log n$ work? You can generalize this to any unweighted grap I think.  
> **username_2**: @SashoNikolov: No. The distance between every two leaves is 2 in a star; but the distance between some leaves in a complete binary tree is less than 2. In general, suppose that there is a graph $G'$ s.t. $d(x, y_i) = 1$ and $d(x_i, x_j) =2$ for every $i,j$. Consider shortest paths from $x$ to $y_i$ in $G'$ (one path for each $i$). These shortest paths cannot share vertices except for $x$ since if $u\neq x$ belongs to shortest paths from $x$ to $y_i$ and $x$ to $y_j$ then $d(y_i, y_j) \leq d(u, y_i) + d(u, y_j) = d(x, y_i) + d(x, y_j) - 2d(x,u) = 2 - 2d(x,u) < 2$. Thus $\deg x \geq n$.  
> **username_3**: hehe, of course you are right, that was silly of me.  

---

## 0 answers

